Graph Crossing Number is a fundamental problem with various applications. In this problem, the goal is to draw an input graph $G$ in the plane so as to minimize the number of crossings between the images of its edges. Despite extensive work, non-trivial approximation algorithms are only known for bounded-degree graphs. Even for this special case, the best current algorithm achieves a $tilde O(sqrt n)$-approximation, while the best current negative result is APX-hardness. All current approximation algorithms for the problem build on the same paradigm: compute a set $E$ of edges (called a emph{planarizing set}) such that $Gsetminus E$ is planar; compute a planar drawing of $Gsetminus E$; then add the drawings of the edges of $E$ to the resulting drawing. Unfortunately, there are examples of graphs, in which any implementation of this method must incur $Omega (text{OPT}^2)$ crossings, where $text{OPT}$ is the value of the optimal solution. This barrier seems to doom the only known approach to designing approximation algorithms for the problem, and to prevent it from yielding a better than $O(sqrt n)$-approximation. In this paper we propose a new paradigm that allows us to overcome this barrier. We show an algorithm that, given a bounded-degree graph $G$ and a planarizing set $E$ of its edges, computes another set $E$ with $Esubseteq E$, such that $|E|$ is relatively small, and there exists a near-optimal drawing of $G$ in which only edges of $E$ participate in crossings. This allows us to reduce the Crossing Number problem to emph{Crossing Number with Rotation System} -- a variant in which the ordering of the edges incident to every vertex is fixed as part of input. We show a randomized algorithm for this new problem, that allows us to obtain an $O(n^{1/2-epsilon})$-approximation for Crossing Number on bounded-degree graphs, for some constant $epsilon>0$.
Download