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, Štirín Castle, Czech Republic , 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
ID Code:237

Repository Staff Only: item control page


Bentley, J. L. and Ottman, T. Algorithms for reporting and counting geometric intersections, IEEE Trans Comput. C-28, (1979), pp 643-647.

Chazelle, B. Reporting and Counting Segmennt Intersections, Journal of Computer and System Sciences, Vol. 32, pp. 156-182, 1986.

Chazelle, B., and Edelsbrunner, H. An Optimal Algorithm for Intersecting Line Segments in the Plane, JACM, 39(1), pp. 1-54, Jan 1992.

Di Battista, G., Eades, P., Tamassia, R., and Tollis, I. G. Graph Drawing: Algorithms for the Visualization of Graphs, Prentice Hall, 1999.

Edelsbrunner, H., and Welzl, E. Halfplanar Range Search in Linear Space and O(n^{0.695}) Query Time," Tech. Univ. Graz, IIG Report 111, 1983.

Gansner, E. R., North, S. C., and Ko, K. P. DAG: A program that draws directed graphs, Software and Experience, 18(11), pp. 1047-1062, Nov 1988.

Garey, M. R., and Johnson, D. S. Crossing number is NP-Complete, SIAM Journal on Algebraic and Discrete Methods, 4, 3 (September 1983), pp. 312-316.

Huang, M. L., Eades, P., and Wang, J., On-line Animated Visualization of Huge Graphs using a Modified Spring Algorithm, Journal of Visual Languages and Computing, Vol 9., pp. 623-645 (1988).

Knuth, D. E., The Art of Computer Programming, Vol. 1: Fundamental Algorithms, Second Ed., pp. 400-401, Addison-Wesley, 1973.

Munzer, T., Exploring Large Graphs in 3D Hyperbolic Space, IEEE Computer Graphics and Applications, Vol. 18 No. 4, 1998.

Preparata, F. P., and Shamos, M. I., Computational geometry - An introduction. Springer-Verlag, New York, 1985.

Rowe, L., et. al., A Browser for Directed Graphs, Software Practice and Experience, Vol. 17(1), pp. 61-76, Jan. 1987.

Schleupen, K., P. Alt, et. al., "High Information Content Color 16.3 inch Desktop AMLCD with 15.7 Million a-Si:H TFTs," Asia Display '98, Digest, Seoul Korea, (1998) pp. 187-191.

Sugiyama, K., Tagawa, S., and M. Toda, Methods for Visual Understanding of Hierarchical Structures, IEEE Transactions on Systems, Man, and Cybernetics, Vol. SMC-11, No. 2. Feb. 1981.