An E log E Line Crossing Algorithm for Levelled Graphs
An E log E Line Crossing Algorithm for Levelled Graphs
复制标题
水平图的E log E线交叉算法
DOI：
10.1007/3-540-46648-7_6
复制
发表时间：
1999
期刊：
影响因子：
--
通讯作者：
A. Malhotra
中科院分区：
文献类型：
--
作者：
V. E. Waddle;A. Malhotra
计算直线段之间的交叉点的数量是计算机科学的几个领域中的一个重要问题。这也是杉山式布局算法的性能瓶颈。本文描述了一种基于边的分类为O（eloge）的水平图的算法，其中e是边的数目。这改进了文献中的最佳算法isO（e1，695loge）。改进的交叉算法实现了Sugiyama风格的算法，可以在当前硬件上在几秒钟内绘制出数万个节点的图形。
Counting the number of crossings between straightline segments is an important problem in several areas of Computer Science. It is also a performance bottleneck for Sugiyama-style layout algorithms. This paper describes an algorithm for leveled graphs, based on the classification of edges that isO(eloge) whereeis the number of edges. This improves on the best algorithm in the literature which isO(e1,695loge). The improved crossing algorithm enabled an implementation of a Sugiyama-style algorithm to lay out graphs of tens of thousands of nodes in a few seconds on current hardware.