Inserting an Edge into a Geometric Embedding
Inserting an Edge into a Geometric Embedding
复制标题
将边插入几何嵌入
DOI：
10.1007/978-3-030-04414-5_29
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Ignaz Rutter
中科院分区：
文献类型：
--
作者：
Marcel Radermacher;Ignaz Rutter
在平面图G中插入一条线性时间内的边，使其交叉数最少的算法[10]，是设计最小化一般图中边交叉数的算法的有用工具。不幸的是，有些图没有几何嵌入，例如交叉数与嵌入数相同。这激发了以下问题的计算复杂性的研究：给定一个组合嵌入图G，计算一个几何嵌入，该几何嵌入具有与G相同的组合嵌入，并且最小化的交叉。我们给出了多项式时间算法的特殊情况下，并证明了一般问题是固定参数听话的交叉数。此外，我们还证明了如何用一个因子来近似交叉数，其中因子是G的最大顶点度。
The algorithm to insert an edgeein linear time into a planar graphGwith a minimal number of crossings one[10], is a helpful tool for designing heuristics that minimize edge crossings in drawings of general graphs. Unfortunately, some graphs do not have a geometric embeddingsuch thathas the same number of crossings as the embedding. This motivates the study of the computational complexity of the following problem: Given a combinatorially embedded graphG, compute a geometric embeddingthat has the same combinatorial embedding asGand that minimizes the crossings of. We give polynomial-time algorithms for special cases and prove that the general problem is fixed-parameter tractable in the number of crossings. Moreover, we show how to approximate the number of crossings by a factor, whereis the maximum vertex degree ofG.
登录
查看更多内容
绘制具有许多共线顶点的平面图
DOI：
--
发表时间：
2016
期刊：
International Symposium Graph Drawing and Network Visualization
影响因子：
--
作者：
G. D. Lozzo;V. Dujmović;Fabrizio Frati;T. Mchedlidze;Vincenzo Roselli
通讯作者：
Vincenzo Roselli
多项式时间内最短两条不相交路径
影响因子：
0.5
作者：
Andreas Björklund;T. Husfeldt
通讯作者：
T. Husfeldt
DOI：
10.1007/bfb0082792
发表时间：
1988
期刊：
--
影响因子：
--
作者：
N. Mnev
通讯作者：
N. Mnev
DOI：
10.1016/j.disopt.2010.05.002
发表时间：
2009-12
期刊：
--
影响因子：
--
作者：
Yusuke Kobayashi;Christian Sommer
通讯作者：
Yusuke Kobayashi;Christian Sommer
DOI：
10.1137/120872310
发表时间：
2012-03
期刊：
ArXiv
影响因子：
--
作者：
Sergio Cabello;B. Mohar
通讯作者：
Sergio Cabello;B. Mohar