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 $G\setminus E'$ is planar; compute a planar drawing of $G\setminus 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 $E'\subseteq 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$.
翻译:图形横跨数字是各种应用程序的根本问题。 在此问题上, 目标是在平面上绘制一个输入图形$G$, 以便最大限度地减少其边缘图像之间的交叉次数。 尽管做了大量的工作, 非三角近似算法只为约束度图形所知道。 即便在这个特殊情况下, 最好的当前算法也能够达到$tilde O( sqrt n), 而目前最佳的负结果是 APX- 硬性 。 所有的当前算法都建立在相同的模式上: 计算一套美元平面的美元( 称为 emph{ planarizal set) 。 这样, 美元平面的平面算法( 美元) 只能通过新平面的平面平面法( 美元) 来减少这个方法的实施 美元( text{ OP_ 2) 的分解法( ), 美元平面的平面图能显示一个更好的平面解决方案。