A subpolynomial approximation algorithm for graph crossing number in low-degree graphs
Open Access
- 9 June 2022
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 303-316
Abstract
We consider the classical Minimum Crossing Number problem: given an n-vertex graph G, compute a drawing of G in the plane, while minimizing the number of crossings between the images of its edges. This is a fundamental and extensively studied problem, whose approximability status is widely open. In all currently known approximation algorithms, the approximation factor depends polynomially on Δ – the maximum vertex degree in G. The best current approximation algorithm achieves an O(n1/2−· (Δ·logn))-approximation, for a small fixed constant є, while the best negative result is APX-hardness, leaving a large gap in our understanding of this basic problem. In this paper we design a randomized O(2O((logn)7/8loglogn)·(Δ))-approximation algorithm for Minimum Crossing Number. This is the first approximation algorithm for the problem that achieves a subpolynomial in n approximation factor (albeit only in graphs whose maximum vertex degree is subpolynomial in n). In order to achieve this approximation factor, we design a new algorithm for a closely related problem called Crossing Number with Rotation System, in which, for every vertex v∈ V(G), the circular ordering, in which the images of the edges incident to v must enter the image of v in the drawing is fixed as part of input. Combining this result with the recent reduction of [Chuzhoy, Mahabadi, Tan ’20] immediately yields the improved approximation algorithm for Minimum Crossing Number.Keywords
All Related Versions
This publication has 19 references indexed in Scilit:
- Hardness of Approximation for Crossing NumberDiscrete & Computational Geometry, 2012
- Crossing numbers2009
- Expander flows, geometric embeddings and graph partitioningJournal of the ACM, 2009
- Crossing number is hard for cubic graphsJournal of Combinatorial Theory, Series B, 2006
- Improved Approximations of Crossings in Graph Drawings and VLSI Layout AreasSIAM Journal on Computing, 2002
- Multicommodity max-flow min-cut theorems and their use in designing approximation algorithmsJournal of the ACM, 1999
- Quickly Excluding a Planar GraphJournal of Combinatorial Theory, Series B, 1994
- Graph minors. V. Excluding a planar graphJournal of Combinatorial Theory, Series B, 1986
- A note of welcomeJournal of Graph Theory, 1977
- Efficient Planarity TestingJournal of the ACM, 1974