Crossing minimization in perturbed drawings
Crossing minimization in perturbed drawings
复制标题
扰动绘图中的交叉最小化
DOI：
10.1007/s10878-020-00586-0
复制
发表时间：
2020
影响因子：
1
通讯作者：
Tóth, Csaba D.
中科院分区：
文献类型：
--
作者：
Fulek, Radoslav;Tóth, Csaba D.
由于数据压缩或分辨率低，在平面上绘制的图形附近的顶点和边缘可能被捆绑到一个共同的节点或弧上。我们用分段线性图来模拟这种“折衷”图。我们希望将一个任意小的图扰动到一个适当的图中（其中顶点是不同的点，任何两条边相交于有限多个点，并且没有三条边有一个共同的内点），以最小化交叉的数量。对于每一个，一个扰动由一个分段线性映射给出，其中是一致范数（即范数）。对于这个优化问题，我们给出了一个多项式时间解。，没有两个相邻的边映射到重叠的弧)。我们还证明了当(i)当(i)是任意图且没有刺时问题是np完全的，当（ii）当(i)有刺且(i)是不相交路径的循环或并时问题是np完全的。
Due to data compression or low resolution, nearby vertices and edges of a graph drawn in the plane may be bundled to a common node or arc. We model such a “compromised” drawing by a piecewise linear map. We wish to perturbby an arbitrarily smallinto a proper drawing (in which the vertices are distinct points, any two edges intersect in finitely many points, and no three edges have a common interior point) that minimizes the number of crossings. An-perturbation, for every, is given by a piecewise linear mapwith, whereis the uniform norm (i.e.,norm). We present a polynomial-time solution for this optimization problem whenGis a cycle and the maphas nospurs(i.e., no two adjacent edges are mapped to overlapping arcs). We also show that the problem becomes NP-complete (i) whenGis an arbitrary graph andhas no spurs, and (ii) whenmay have spurs andGis a cycle or a union of disjoint paths.
登录
查看更多内容
如何绘制平面聚类图
DOI：
--
发表时间：
1995
期刊：
International Computing and Combinatorics Conference
影响因子：
--
作者：
Qing;R. Cohen;P. Eades
通讯作者：
P. Eades
嵌入式平面图的带状平面度测试
影响因子：
1.1
作者：
Patrizio Angelini;G. D. Lozzo;G. Battista;Fabrizio Frati
通讯作者：
Fabrizio Frati
管道的簇平面度
影响因子：
1.1
作者：
Patrizio Angelini;Giordano Da Lozzo
通讯作者：
Giordano Da Lozzo
DOI：
10.1137/120872310
发表时间：
2012-03
期刊：
ArXiv
影响因子：
--
作者：
Sergio Cabello;B. Mohar
通讯作者：
Sergio Cabello;B. Mohar
聚类图的平面性
DOI：
--
发表时间：
1995
期刊：
Embedded Systems and Applications
影响因子：
--
作者：
Qing;R. Cohen;P. Eades
通讯作者：
P. Eades