Computing crossing numbers in quadratic time

DOI10.1145/380752.380805zbMath1323.68314OpenAlexW2083578892MaRDI QIDQ5175973

Martin Grohe

Publication date: 27 February 2015

Published in: Proceedings of the thirty-third annual ACM symposium on Theory of computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/380752.380805

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Planar graphs; geometric and topological aspects of graph theory (05C10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (13)

Two recursive inequalities for crossing numbers of graphs ⋮ Recognizing and drawing IC-planar graphs ⋮ Decidability of string graphs ⋮ FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ Recent Advances in Exact Crossing Minimization (Extended Abstract) ⋮ Parameterized Leaf Power Recognition via Embedding into Graph Products ⋮ A branch-and-cut approach to the crossing number problem ⋮ The crossing number of \(K_{1,4,n}\) ⋮ MSOL restricted contractibility to planar graphs ⋮ Crossing Numbers and Parameterized Complexity ⋮ Connecting the dots (with minimum crossings) ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover ⋮ Parameterized leaf power recognition via embedding into graph products

Cites Work

• A constant-factor approximation algorithm for the k -median problem (extended abstract)

This page was built for publication: Computing crossing numbers in quadratic time