## An E log E Line Crossing Algorithm for Levelled Graphs
Waddle, Vance and Malhotra, Ashok
(1999)
Full text not available from this repository. ## AbstractCounting 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.
Repository Staff Only: item control page References |