An algorithm for the graph crossing number problem

DOI10.1145/1993636.1993678MaRDI QIDQ5419100zbMATH OpenOpenAlexFDO

Authors 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) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20) Approximation algorithms (68W25)

Abstract: We study the Minimum Crossing Number problem: given an $n$-vertex graph $G$, the goal is to find a drawing of $G$ in the plane with minimum number of edge crossings. This is one of the central problems in topological graph theory, that has been studied extensively over the past three decades. The first non-trivial efficient algorithm for the problem, due to Leighton and Rao, achieved an $O(nlo{g}^{4}n)$-approximation for bounded degree graphs. This algorithm has since been improved by poly-logarithmic factors, with the best current approximation ratio standing on $O(npoly(d)lo{g}^{3/2}n)$ for graphs with maximum degree $d$. In contrast, only APX-hardness is known on the negative side. In this paper we present an efficient randomized algorithm to find a drawing of any $n$-vertex graph $G$ in the plane with $O(OP{T}^{10}cdotpoly(dlogn))$ crossings, where $OPT$ is the number of crossings in the optimal solution, and $d$ is the maximum vertex degree in $G$. This result implies an $ildeO(n^{9/10}poly(d))$-approximation for Minimum Crossing Number, thus breaking the long-standing $ildeO(n)$-approximation barrier for bounded-degree graphs.

Recommendations

• On graph crossing number and edge planarization
• On the Crossing Number of Almost Planar Graphs
• Approximating the crossing number of graphs embeddable in any orientable surface
• Approximating the rectilinear crossing number
• Improved approximations of crossings in graph drawings

Cited in

(41)

• Algorithms for crossover point determination
• Crossing numbers and stress of random graphs
• Hardness of approximation for crossing number
• Crossing number for graphs with bounded pathwidth
• Exact crossing number parameterized by vertex cover
• Approximating the rectilinear crossing number
• Inapproximability ratios for crossing number
• Approximating the fixed linear crossing number
• Algorithms for graphs embeddable with few crossings per edge
• Approximating the maximum rectilinear crossing number
• The Bundled Crossing Number
• Approximating the rectilinear crossing number
• An algorithmic development to minimize crossings in electronic circuits
• Improved approximations of crossings in graph drawings
• scientific article; zbMATH DE number 3646924 (Why is no real title available?)
• Approximating the Crossing Number of Apex Graphs
• scientific article; zbMATH DE number 1500685 (Why is no real title available?)
• Planar crossing numbers of graphs of bounded genus
• Approximation algorithms for Euler genus and related problems
• An ILP-based Proof System for the Crossing Number Problem
• Improved Approximations of Crossings in Graph Drawings and VLSI Layout Areas
• Algorithmic Aspects of the Intersection and Overlap Numbers of a Graph
• scientific article; zbMATH DE number 7278018 (Why is no real title available?)
• Computing crossing numbers in quadratic time
• Polylogarithmic approximation for Euler genus on bounded degree graphs
• On graph crossing number and edge planarization
• Approximating the Crossing Number of Toroidal Graphs
• Algorithms for the Hypergraph and the Minor Crossing Number Problems
• Approximating the crossing number of graphs embeddable in any orientable surface
• Fundamentals of Computation Theory
• An algorithmic meta-theorem for graph modification to planarity and FOL
• Crossing minimization in perturbed drawings
• Graph Drawing
• Algorithms and Computation
• Approximating the Bundled Crossing Number
• Inserting Multiple Edges into a Planar Graph
• Parameterised partially-predrawn crossing number
• Vertex insertion approximates the crossing number of apex graphs
• Approximating the crossing number of dense graphs (poster abstract)
• An algorithmic meta-theorem for graph modification to planarity and FOL
• An algorithm for estimating the crossing number of dense graphs, and continuous analogs of the crossing and rectilinear crossing numbers

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5419100)