Journal of Graph Algorithms and Applications Global K-level Crossing Reduction
Journal of Graph Algorithms and Applications Global K-level Crossing Reduction
复制标题
图算法与应用杂志 全局 K 级交叉减少
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
Brandenburg
中科院分区：
文献类型：
--
作者：
C. Bachmaier;F. Brandenburg;Wolfgang Brunner;Ferdinand Hübner;M. S. Rahman;S. Fujita;Ferdinand Huebner@bedag Ch;Ferdinand Hübner ) 632 Bachmaier;Brandenburg
有向图通常由Sugiyama等人在1981年引入的四阶段框架绘制。顶点放置在平行的水平标高上。通过求解单侧2级交叉最小化问题来计算连续级之间的边缘路由，该问题在所有级上的上下扫描中重复。交叉极小化问题一般是NP-困难的。我们引入了一个全球交叉减少，在任何特定的时间，考虑所有级别之间的所有交叉。我们的方法是基于筛选技术。与逐层单侧2层交叉减少算法相比，它在交叉次数上提高了5 - 10%。此外，它避免了类型2冲突，即端点为虚拟顶点的边之间的交叉。这有助于拉直跨越多个级别的长边。最后，全局交叉减少方法可以直接扩展到循环，径向和聚类水平图实现类似的改进。运行时间是输入图大小的二次方，而常见的逐层方法更快，但操作更大的图，具有许多长边的虚拟顶点。由德国研究共同体（DFG）资助，赠款Br835/15 - 1。初步版本[3]在WALCOM 2010算法和计算研讨会上提出。
Directed graphs are commonly drawn by a four phase framework introduced by Sugiyama et al. in 1981. The vertices are placed on parallel horizontal levels. The edge routing between consecutive levels is computed by solving one-sided 2-level crossing minimization problems, which are repeated in up and down sweeps over all levels. Crossing minimization problems are generally N P-hard. We introduce a global crossing reduction, which at any particular time considers all crossings between all levels. Our approach is based on the sifting technique. It yields an improvement of 5 – 10% in the number of crossings over the level-by-level one-sided 2-level crossing reduction heuristics. In addition, it avoids type 2 conflicts which are crossings between edges whose endpoints are dummy vertices. This helps straightening long edges spanning many levels. Finally, the global crossing reduction approach can directly be extended to cyclic, radial, and clustered level graphs achieving similar improvements. The running time is quadratic in the size of the input graph, whereas the common level-by-level approaches are faster but operate on larger graphs with many dummy vertices for long edges. Supported by the Deutsche Forschungsgemeinschaft (DFG), grant Br835/15-1. A preliminary version [3] was presented at the Workshop on Algorithms and Computation, WALCOM 2010.
网格筛选：平整和交叉减少
DOI：
10.1145/2133803.2345682
发表时间：
2012
期刊：
ACM J. Exp. Algorithmics
影响因子：
--
作者：
C. Bachmaier;W. Brunner;A. Gleißner
通讯作者：
A. Gleißner