Computing crossing numbers in quadratic time

2001/07/06 by Martin Grohe · 7 citations
Computer Science · Mathematics · #Advanced Graph Theory Research #Algorithm #Combinatorics #Computational Geometry and Mesh Generation #Computer science #Crossing number (knot theory) #Data Management and Algorithms #Discrete mathematics #Geometry #Graph #Mathematics #Plane (geometry) #Quadratic equation #Time complexity

paper · doi:10.1145/380752.380805

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

Abstract

We show that for every fixed k≥ 0 there is a quadratic time algorithm that decides whether 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.

Citations

• Efficient Planarity Testing
• Nonconstructive tools for proving polynomial-time decidability
• Graph minors. V. Excluding a planar graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The graph genus problem is NP-complete
• Mathematical Logic

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
• Computing crossing number in linear time
• Invitation to Fixed-Parameter Algorithms
• The Early History of the Brick Factory Problem
• Logic of graphs [wikipedia]