Crossing minimization in extended level drawings of graphs
Crossing minimization in extended level drawings of graphs
复制标题
扩展级图形绘图中的交叉最小化
DOI：
10.1016/j.dam.2009.09.002
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
S.-H. Hong
中科院分区：
文献类型：
--
作者：
C. Bachmaier;H. Buchner;M. Forster;S.-H. Hong
绘制有向图最流行的方法是将顶点放置在一组水平或同心水平上，称为水平绘制。由于层次图在图的层次可视化方面的强大应用，层次图在图画学中得到了广泛的研究。有两种绘制约定：水平绘制使用一组平行线，而放射状绘制使用一组同心圆。在标高图形中，仅允许在不同标高上的顶点之间使用边。然而，许多现实世界的图表显示了层次结构，顶点之间的边在同一级别上。在这篇文章中，我们提出了图的扩展层次图的新问题，该问题被作为社会网络可视化中的公开问题之一来解决，特别是显示参与者的中心值。更具体地说，我们研究了图的扩展平面图的边交点数的最小化问题。主要问题可以表述为两个相邻层次之间的扩展单边交叉最小化问题，因为它是与平面图中的单边交叉最小化问题一样的民间传说。首先证明了扩展的单边交叉最小化问题对于水平图和放射状图都是NP难的，然后给出了最小化扩展水平图中的边交叉的有效启发式算法。我们广泛的实验结果表明，我们的新方法减少了高达30%的边缘交叉。
The most popular method of drawing directed graphs is to place vertices on a set of horizontal or concentric levels, known as level drawings. Level drawings are well studied in Graph Drawing due to their strong application for the visualization of hierarchy in graphs. There are two drawing conventions: Horizontal drawings use a set of parallel lines and radial drawings use a set of concentric circles. In level drawings, edges are only allowed between vertices on different levels. However, many real world graphs exhibit hierarchies with edges between vertices on the same level. In this paper, we initiate the new problem of extended level drawings of graphs, which was addressed as one of the open problems in social network visualization, in particular, displaying centrality values of actors. More specifically, we study minimizing the number of edge crossings in extended level drawings of graphs. The main problem can be formulated as the extended one-sided crossing minimization problem between two adjacent levels, as it is folklore with the one-sided crossing minimization problem in horizontal drawings. We first show that the extended one-sided crossing minimization problem is NP-hard for both horizontal and radial drawings, and then present efficient heuristics for minimizing edge crossings in extended level drawings. Our extensive experimental results show that our new methods reduce up to 30% of edge crossings.
登录
查看更多内容
径向布局中的近似交叉最小化
DOI：
--
发表时间：
2008
期刊：
Latin American Symposium on Theoretical Informatics
影响因子：
--
作者：
Seok;H. Nagamochi
通讯作者：
H. Nagamochi
08191 执行摘要 - 图形绘制及其在生物信息学和社会科学中的应用
DOI：
--
发表时间：
2008
期刊：
Graph Drawing with Applications to Bioinformatics and Social Sciences
影响因子：
--
作者：
S. Borgatti;S. Kobourov;O. Kohlbacher;Petra Mutzel
通讯作者：
Petra Mutzel
DOI：
--
发表时间：
--
期刊：
Discrete and Computational Geometry (発行予定)
影响因子：
--
作者：
L.Zhao;H.Nagamochi;T.Ibaraki;H.Nagamochi;H.Nagamochi
通讯作者：
H.Nagamochi
一种最小化二分图中交叉弧数的分支定界算法
DOI：
--
发表时间：
1996
期刊：
影响因子：
--
作者：
V. Valls;R. Martí;P. Lino
通讯作者：
P. Lino