An E log E Line Crossing Algorithm for Levelled Graphs

Waddle, Vance and Malhotra, Ashok (1999) An E log E Line Crossing Algorithm for Levelled Graphs. In: Graph Drawing 7th International Symposium, GD’99, September 15-19, 1999 , pp. 59-71(Official URL:

Full text not available from this repository.


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 clasification of edges that is O(e log e) where e is the number of edges. This improves on the best algorithm in the literature which is O(e^{1.695}log e). The improved crossing algorithm enabled an implementation of a Sugiyama-style algorithm to lay auf graphs of tens of thousands of nodes in a few seconds on current hardware.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-46648-7_6
Classifications: M Methods > M.500 Layered
G Algorithms and Complexity > G.420 Crossings
P Styles > P.480 Layered

Actions (login required)

View Item View Item