Crossing Number in Slightly Superexponential Time (Extended Abstract)

A drawing of an (undirected) graph G is a mapping φ that assigns to each vertex a distinct point in the plane and to each edge uw a continuous curve φ(uv) in the plane from φ(u) to φ(v), not passing through the image of any other vertex. Two edges e and f cross in a point p if p ∈ φ(e) ∩ φ(f ) and p is not the image of a vertex of G. In a drawing no three edges are allowed to cross in the same point. The crossing number of a drawing of G is the number of points p such that some two edges e and f cross in p. In the Crossing Number problem, the input consists of a graph G and integer k. The task is to determine whether there exists a drawing of G with crossing number at most k, and to output such a drawing if it exists.

Grohe [STOC 2001, JCSS 2004] gave an algorithm for Crossing Number with running time f (k)n 2 where k) . He conjectured that there exists an algorithm with running time 2 O(k) n. Kawarabayashi and Reed [STOC 2007] outlined an algorithm with running time f (k)n where f (k) = 2 2 2 Ω(k) . Combining the main combinatorial lemma by Kawarabayashi and Reed with the recent algorithm for Crossing Number parameterized treewidth plus k by de Verdière and Magnard [ESA 2021] would yield a running time of f (k)n where f (k) = 2 O(k 4 log k) . This still falls far away from the dependency on k in the conjecture by Grohe. Furthermore, critical details of the proof of the correctness of the algorithm of Kawarabayashi and Reed, and, in particular, of the aforementioned combinatorial lemma, have never been published.

In this work, we give an algorithm with running time 2 O(k log k) n. Thus, our algorithm resolves Grohe's 23-year old conjecture up to a logarithmic factor in k in the exponent. .