A tighter insertion-based approximation of the crossing number
A tighter insertion-based approximation of the crossing number
复制标题
交叉数的更紧密的基于插入的近似
DOI：
10.1007/s10878-016-0030-z
复制
发表时间：
2017
影响因子：
1
通讯作者：
P. Hlinĕný
中科院分区：
文献类型：
--
作者：
M. Chimani;P. Hlinĕný
画一个平面图和一组附加的边。多边插入问题（MEI）要求用最小数量的成对边相交来绘制一个平面，这样就可以对其进行子绘制。找到MEI的精确解对于一般的alf来说是np困难的。我们提出了第一个用于MEI的多项式时间算法，该算法实现了一个加性逼近保证-仅依赖于f的大小和g的最大程度，在connectedG的情况下。我们的算法似乎也是这个领域中第一个直接实现的算法，仅次于单边插入。我们还知道，MEI问题的（甚至近似）解将近似f -近平面图的交叉数，而精确计算的交叉数已经是np困难的。因此，我们的算法为近平面图的交叉数问题引入了新的、改进的逼近界，实现了对有界度和有界大小的大类图的常因子逼近。
LetGbe a planar graph andFa set of additional edges not yet inG. Themultiple edge insertionproblem (MEI) asks for a drawing ofwith the minimum number of pairwise edge crossings, such that the subdrawing ofGis plane. Finding an exact solution to MEI is NP-hard for generalF. We present the first polynomial time algorithm for MEI that achieves an additive approximation guarantee—depending only on the size ofFand the maximum degree ofG, in the case of connectedG. Our algorithm seems to be the first directly implementable one in that realm, too, next to the single edge insertion. It is also known that an (even approximate) solution to the MEI problem would approximate the crossing number of theF-almost-planar graph, while computing the crossing number ofexactly is NP-hard already when. Hence our algorithm induces new, improved approximation bounds for the crossing number problem ofF-almost-planar graphs, achieving constant-factor approximation for the large class of such graphs of bounded degrees and bounded size ofF.
登录
查看更多内容
DOI：
10.1007/978-3-540-24595-7_2
发表时间：
2003-09
期刊：
--
影响因子：
--
作者：
Carsten Gutwenger;Petra Mutzel
通讯作者：
Carsten Gutwenger;Petra Mutzel
SPQR树在图形绘制平面化方法中的应用
DOI：
10.17877/de290r-15654
发表时间：
2010
期刊：
J. Graph Algorithms Appl.
影响因子：
--
作者：
Carsten Gutwenger
通讯作者：
Carsten Gutwenger
图线性嵌入中的交叉最小化
DOI：
10.1109/12.46286
发表时间：
1990
期刊：
IEEE Trans. Computers
影响因子：
--
作者：
S. Masuda;K. Nakajima;T. Kashiwabara;T. Fujisawa
通讯作者：
T. Fujisawa
DOI：
10.1016/j.endm.2007.07.037
发表时间：
2007
期刊：
Electron. Notes Discret. Math.
影响因子：
--
作者：
I. Gitler;Petr Hliněný;J. Leaños;G. Salazar
通讯作者：
G. Salazar
DOI：
10.1137/120872310
发表时间：
2012-03
期刊：
ArXiv
影响因子：
--
作者：
Sergio Cabello;B. Mohar
通讯作者：
Sergio Cabello;B. Mohar