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 reports@us.ibm.com .