论文标题
低度图中图形交叉数的子多物质近似算法
A Subpolynomial Approximation Algorithm for Graph Crossing Number in Low-Degree Graphs
论文作者
论文摘要
我们考虑经典的最小交叉数问题：给定$ n $ vertex图$ g $，计算飞机上$ g $的图形，同时最大程度地减少其边缘图像之间的交叉数量。这是一个基本且广泛研究的问题，其近似性状态被广泛开放。在当前已知的近似算法中，近似因子在$δ$上取决于$ g $的最大顶点度。最佳当前近似算法实现了$ O（n^{1/2- \ varepsilon} \ cdot \ cdot \ cdot \ text {poly}（δ\ cdot \ log n））$ - 近似值，对于一个小的固定常数$ε$，而最佳的负面结果是APX-HADNESS，这是我们的apx-Hardness，留下了我们很大的问题。在本文中，我们设计了一个随机的$ o \ left（2^{o（（（\ log n）^{7/8} \ log \ log \ log n）} \ cdot \ cdot \ text {poly}（δ）\ right）$ - 近似算法的最小交叉数量。这是第一个以$ n $ n $近似因子达到子多项式问题的问题的近似算法（尽管仅在最大顶点度为$ n $的最大顶点程度的图中）。 为了实现此近似因素，我们为一个与旋转系统交叉数字的紧密相关的问题设计了一种新算法，在该问题中，对于每个顶点$ v \ in V（g）$中的每个顶点$ v \，圆形订购，其中边缘的图像在$ v $中必须输入$ v $的图像中的$ v $的图像中的图像中的一部分是输入的一部分。将此结果与最近的[Chuzhoy，Mahabadi，Tan '20]的减少结合起来，立即产生了改进的近似算法，以减少交叉数。我们介绍了几种新的技术工具，我们希望将来有助于为该问题获得更好的算法。
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-\varepsilon}\cdot \text{poly}(Δ\cdot\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\left(2^{O((\log n)^{7/8}\log\log n)}\cdot\text{poly}(Δ)\right )$-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$). In order to achieve this approximation factor, we design a new algorithm for a closely related problem called Crossing Number with Rotation System, in which, for every vertex $v\in V(G)$, the circular ordering, in which the images of the edges incident to $v$ must enter the image of $v$ in the drawing is fixed as part of the input. Combining this result with the recent reduction of [Chuzhoy, Mahabadi, Tan '20] immediately yields the improved approximation algorithm for Minimum Crossing Number. We introduce several new technical tools, that we hope will be helpful in obtaining better algorithms for the problem in the future.
