How to Layer a Directed Acyclic Graph

Healy, Patrick and Nikolov, Nikola S. (2002) How to Layer a Directed Acyclic Graph. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 16-30 (Official URL:

Full text not available from this repository.


We consider the problem of partitioning a directed acyclic graph into layers such that all edges point unidirectionally. We perform an experimental analysis of some of the existing layering algorithms and then propose a new algorithm that is more realistic in the sense that it is possible to incorporate specific information about node and edge widths into the algorithm. The goal is to minimize the total sum of edge spans subject to dimension constraints on the drawing. We also present some preliminary results from experiments we have conducted using our layering algorithm on over 5900 example directed acyclic graphs

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_2
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.630 Labeling
P Styles > P.480 Layered
ID Code:369

Repository Staff Only: item control page


G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Computational Geometry: Theory and Applications, (7):303-316, 1997.

Fr. Brandenburg, Ul. Brandes, M. Himsolt, and M. Raitner. Graph-drawing contest report. In Joe Marks, editor, Graph Drawing: Proceedings of 8th International Symposium, GD 2000, pages 410-418. Springer-Verlag, 2000.

E.G. Coffman and R.L. Graham. Optimal scheduling for two processor systems. Acta Informatica, 1:200-213, 1972.

P. Eades and K. Sugiyama. How to draw a directed graph. Journal of Information Processing, 13(4):424-437, 1990.

E. Gansner, E. Koutsofios, S. North, and K. Vo. A technique for drawing directed graphs. IEEE Transactions on Software Engineering, 19(3):214-229, March 1993.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man, and Cybernetics, SMC-11(2):109-125, February 1981.