A Global k-Level Crossing Reduction Algorithm
A Global k-Level Crossing Reduction Algorithm
复制标题
一种全局k级交叉约简算法
DOI：
--
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
Ferdinand Hübner
中科院分区：
文献类型：
--
作者：
C. Bachmaier;F. Brandenburg;Wolfgang Brunner;Ferdinand Hübner
有向图通常由Sugiyama算法绘制，其中交叉减少是一个关键阶段。它是通过重复的单侧2级交叉最小化来完成的，这仍然是${mathcal{NP}}$-hard。
我们引入了一个全球交叉减少，在任何特定的时间捕获所有的交叉点，特别是长边。我们的方法是基于筛选技术，并通过进一步减少5 - 10%的交叉点的数量，提高了层次框架中的逐层分类。此外，它避免了类型2的冲突，这有助于拉直的边缘，并有一个运行时间，这是二次的输入图的大小独立的虚拟顶点。最后，该方法可以直接扩展到循环，径向和聚类水平图，它实现了类似的改进，在以前的算法。
Directed graphs are commonly drawn by the Sugiyama algorithm, where crossing reduction is a crucial phase. It is done by repeated one-sided 2-level crossing minimizations, which are still ${mathcal{NP}}$-hard.
We introduce a global crossing reduction, which at any particular time captures all crossings, especially for long edges. Our approach is based on the sifting technique and improves the level-by-level heuristics in the hierarchic framework by a further reduction of the number of crossings by 5 – 10%. In addition it avoids type 2 conflicts which help to straighten the edges, and has a running time which is quadratic in the size of the input graph independently of dummy vertices. Finally, the approach can directly be extended to cyclic, radial, and clustered level graphs where it achieves similar improvements over the previous algorithms.