An algorithm for the graph crossing number problem

DOI10.1145/1993636.1993678zbMath1288.68259arXiv1012.0255OpenAlexW1976460919MaRDI QIDQ5419100

Julia Chuzhoy

Publication date: 5 June 2014

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

Full work available at URL: https://arxiv.org/abs/1012.0255

zbMATH Keywords

approximation algorithmgraph crossing number

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Randomized algorithms (68W20)

Related Items (14)

Approximation Algorithms for Euler Genus and Related Problems ⋮ Inserting Multiple Edges into a Planar Graph ⋮ Unnamed Item ⋮ The Bundled Crossing Number ⋮ Approximating the Rectilinear Crossing Number ⋮ Hardness of approximation for crossing number ⋮ Exact crossing number parameterized by vertex cover ⋮ Planar crossing numbers of graphs of bounded genus ⋮ Crossing numbers and stress of random graphs ⋮ Crossing minimization in perturbed drawings ⋮ Crossing number for graphs with bounded pathwidth ⋮ A tighter insertion-based approximation of the crossing number ⋮ Unnamed Item ⋮ Approximating the rectilinear crossing number

This page was built for publication: An algorithm for the graph crossing number problem