2022/02/14 by Julia Chuzhoy, Zihan Tan, Chuzhoy, Julia +1
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.2202.06827
openalex publication_date 2022/02/14 · openalex created_date 2022/05/05 · openalex updated_date 2026/07/28
We consider the classical Minimum Crossing Number problem: given an\nn-vertex graph G, compute a drawing of G in the plane, while minimizing\nthe number of crossings between the images of its edges. This is a fundamental\nand extensively studied problem, whose approximability status is widely open.\nIn all currently known approximation algorithms, the approximation factor\ndepends polynomially on \Δ -- the maximum vertex degree in G. The best\ncurrent approximation algorithm achieves an O(n1/2-\ε\⋅\n\poly(\Δ\⋅\log n))-approximation, for a small fixed constant\n\ε, while the best negative result is APX-hardness, leaving a large gap\nin our understanding of this basic problem. In this paper we design a\nrandomized O\(2^O((\log n)7/8\log\log\nn)\⋅\poly(\Δ) )-approximation algorithm for Minimum\nCrossing Number. This is the first approximation algorithm for the problem that\nachieves a subpolynomial in n approximation factor (albeit only in graphs\nwhose maximum vertex degree is subpolynomial in n).\n In order to achieve this approximation factor, we design a new algorithm for\na closely related problem called Crossing Number with Rotation System, in\nwhich, for every vertex v\∈ V(G), the circular ordering, in which the images\nof the edges incident to v must enter the image of v in the drawing is\nfixed as part of the input. Combining this result with the recent reduction of\n[Chuzhoy, Mahabadi, Tan '20] immediately yields the improved approximation\nalgorithm for Minimum Crossing Number. We introduce several new technical\ntools, that we hope will be helpful in obtaining better algorithms for the\nproblem in the future.\n