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

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