A subpolynomial approximation algorithm for graph crossing number in low-degree graphs

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 ( n 1/2− · (Δ·log n ))-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 (2 O ((log n ) 7/8 loglog n ) ·(Δ))-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 ).

Authors

• Julia Chuzhoy
• Zihan Tan

Keywords

• Approximation Algorithm
• Crossing Number