The Constrained Crossing Minimization Problem
The Constrained Crossing Minimization Problem
复制标题
约束交叉最小化问题
DOI：
10.1007/3-540-46648-7_18
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
T. Ziegler
中科院分区：
文献类型：
--
作者：
Petra Mutzel;T. Ziegler
在本文中，我们考虑的约束交叉最小化问题定义如下。给定一个连通平面图G =（V，E），G的一个组合嵌入II（G），和一组两两不同的边F <$V × V，求G′ =（V，E <$F）的一个图，使得G的组合嵌入II（G）保持不变，且边交叉数最小。在基于平面化的图形绘制方法中，存在约束交叉极小化问题。在[4]中，我们已经表明，我们可以将约束交叉最小化问题表示为|F|-pairs最短路径问题，其中我们希望最小化路径长度加上路径之间交叉点的数量之和
In this paper we consider the constrained crossing minimization problem defined as follows. Given a connected planar graph G = (V,E), a combinatorial embedding II(G) of G, and a set of pairwise distinct edges F ⊆ V × V, find a drawing of G′ = (V,E ∼ F) such that the combinatorial embedding II(G) of G is preserved and the number of edge crossings is minimized. The constrained crossing minimization problem arises in the graph drawing method based on planarization. In [4] we have shown that we can formulate the constrained crossing minimization problem as an |F|-pairs shortest walks problem, where we want to minimize the sum of the lengths of the walks plus the number of crossings between the walks