论文标题
迈向图形越过数的近似
Towards Better Approximation of Graph Crossing Number
论文作者
论文摘要
图形交叉数是各种应用程序的基本问题。在这个问题中，目标是在平面中绘制输入图$ g $，以最大程度地减少其边缘图像之间的交叉数。尽管进行了广泛的工作，但非平凡近似算法仅以有限度图而闻名。即使对于这种特殊情况，最佳当前算法也达到了$ \ tilde o（\ sqrt n）$ - 近似值，而最佳当前负面结果是APX硬度。该问题的所有当前近似算法在同一范式上构建：计算一个$ e'$的边缘（称为a \ emph {planarized set}），以便$ g \ setminus e'$ is planar;计算$ g \ setminus e'$的平面图；然后将$ e'$边缘的图纸添加到生成的图纸中。不幸的是，有图形的示例，其中此方法的任何实现都必须产生$ω（\ text {opt}^2）$交叉，其中$ \ text {opt} $是最佳解决方案的值。这种障碍似乎注定了为问题设计近似算法的唯一已知方法，并防止其产生的效果比$ O（\ sqrt n）$ - 近似更好。 在本文中，我们提出了一个新的范式，使我们能够克服这一障碍。我们展示了一种算法，鉴于有界的图形$ g $和一个平面化的边缘的$ e'$，计算另一个套装$ e''$带有$ e'\ subseteq e''$，使得$ | e''| $相对较小，并且在$ g $中的近乎$ g $的$ g $ cross of Edges of Edges of Edges of Edges of Edges of Edges of Edges of Edges''''''''''''这使我们能够将交叉数量问题减少到\ emph {与旋转系统的交叉数} - 一个变体，其中，在每个顶点的边缘的订购是作为输入的一部分固定的。我们显示了一个新问题的随机算法，该算法使我们能够获得一个$ o（n^{1/2-ε}）$ - 在有限度图上交叉数的近似值，对于某些常数$ε> 0 $。
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 $Ω(\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-ε})$-approximation for Crossing Number on bounded-degree graphs, for some constant $ε>0$.
