An E Log E Line Crossing Algorithm for Leveled Graphs

        Counting the number of crossings between straightline segments is an important problem in several areas of Computer Science. Algorithms in the literature are of order O(e2) where e is the number of edges. This paper describes a sweep algorithm for leveled graphs, based on the classification of edges that is order O(e In n) where n is the number of nodes.

By: Vance Waddle and Ashok Malhotra

Published in: Lecture Notes in Computer Science, volume 1731, (no ), pages 59-71 in 1999

Please obtain a copy of this paper from your local library. IBM cannot distribute this paper externally.

Questions about this service can be mailed to .