Computing crossing numbers in quadratic time

DOI10.1016/j.jcss.2003.07.008zbMath1073.68064OpenAlexW4213236916WikidataQ57255587 ScholiaQ57255587MaRDI QIDQ1887712

Martin Grohe

Publication date: 22 November 2004

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2003.07.008

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Related Items (27)

FPT Suspects and Tough Customers: Open Problems of Downey and Fellows ⋮ Crossing Minimization for 1-page and 2-page Drawings of Graphs with Bounded Treewidth ⋮ Properties of Large 2-Crossing-Critical Graphs ⋮ Parameterized analysis and crossing minimization problems ⋮ Deciding Parity of Graph Crossing Number ⋮ Approximation Algorithms for Euler Genus and Related Problems ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Sublinear approximation algorithms for boxicity and related problems ⋮ Obtaining a Planar Graph by Vertex Deletion ⋮ Grid recognition: classical and parameterized computational perspectives ⋮ Hardness of approximation for crossing number ⋮ Obtaining a planar graph by vertex deletion ⋮ The early history of the brick factory problem ⋮ Graph operations on parity games and polynomial-time algorithms ⋮ Maximum Cut Parameterized by Crossing Number ⋮ Exact crossing number parameterized by vertex cover ⋮ Planar crossing numbers of graphs of bounded genus ⋮ Approximating the Crossing Number of Toroidal Graphs ⋮ Crossing minimization in perturbed drawings ⋮ Crossing number for graphs with bounded pathwidth ⋮ On the parameterized complexity of layered graph drawing ⋮ A Practical Approach to Courcelle's Theorem ⋮ Chordal deletion is fixed-parameter tractable ⋮ Crossing number is hard for cubic graphs ⋮ The parameterized complexity of \(k\)-edge induced subgraphs ⋮ Unnamed Item ⋮ A Linear-Time Parameterized Algorithm for Node Unique Label Cover

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. V. Excluding a planar graph
• A simpler proof of the excluded minor theorem for higher surfaces
• The monadic second-order logic of graphs. XII: Planar graphs and planar maps
• Graph minors. XIII: The disjoint paths problem
• The graph genus problem is NP-complete
• Query evaluation via tree-decompositions
• Nonconstructive tools for proving polynomial-time decidability
• Efficient Planarity Testing
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The NP-completeness column: An ongoing guide

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