Computing crossing number in linear time

2007/06/11 by Ken‐ichi Kawarabayashi, Buce Reed · 5 citations
Computer Science · Mathematics · #Computational Geometry and Mesh Generation #Advanced Graph Theory Research #Advanced Combinatorial Mathematics

paper · doi:10.1145/1250790.1250848

openalex publication_date 2007/06/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29

Abstract

We show that for every fixed k, there is a linear time algorithm that decides whether or not a given graph has crossing number at most k, and if this is the case, computes a drawing of the graph in the plane with at most k crossings. This answers the question posed by Grohe (STOC'01 and JCSS 2004). Our algorithm can be viewed as a generalization of the seminal result by Hopcroft and Tarjan lin1, which determines if a given graph is planar in linear time.

Citations

• Efficient Planarity Testing
• Systems of Circuits on Two-Dimensional Manifolds
• Embedding grids in surfaces
• A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface
• Computing crossing numbers in quadratic time

Cited by

• Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth
• Fixed Parameter Tractability of Crossing Minimization of Almost-Trees
• On the Parameterized Complexity of Layered Graph Drawing
• Linkless and flat embeddings in 3-space and the unknot problem
• Logic of graphs [wikipedia]

Related

• Computing Crossing Numbers in Quadratic Time
• On Graph Crossing Number and Edge Planarization
• An Algorithm for the Graph Crossing Number Problem
• Crossing Number for Graphs With Bounded Pathwidth
• Crossing Numbers of Beyond Planar Graphs Re-revisited: A Framework Approach