Abstract
In this paper we consider the class of directed acyclic graphs (DAGs), and present the results of an experimental study on four drawing algorithms specifically developed for DAGs. Our study is conducted on two large test suites of DAGs and yields more than 30 charts comparing the performance of the drawing algorithms with respect to several quality measures, including area, crossings, bends, and aspect ratio. The algorithms exhibit various trade-offs with respect to the quality measures, and none of them clearly outperforms the others.
Research supported in part by the National Science Foundation under grant CCR-9423847, by the U.S. Army Research Office under grant DAAH04-96-1-0013, by ESPRIT LTR of the European Community under Project no. 20244 (ALCOM-IT), by the NATO-CNR Advanced Fellowships Programme, and by a gift from Tom Sawyer Software.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
P. Bertolazzi, R. F. Cohen, G. Di Battista, R. Tamassia, and I. G. Tollis. How to draw a series-parallel digraph. Internat. J. Comput. Geom. Appl., 4:385–402, 1994.
F. J. Brandenburg, M. Himsolt, and C. Rohrer. An experimental comparison of force-directed and randomized graph drawing algorithms. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes in Computer Science, pages 76–87. Springer-Verlag, 1996.
L. Buti, G. Di Battista, G. Liotta, E. Tassinari, F. Vargiu, and L. Vismara. GD-Workbench: A system for prototyping and testing graph drawing algorithms. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of LNCS, pages 111–122. Springer-Verlag, 1996.
M. Chrobak, M. T. Goodrich, and R. Tamassia. Convex drawings of graphs in two and three dimensions. In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 319–328, 1996.
G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Algorithms for drawing graphs: An annotated bibliography. Comput. Geom. Theory Appl., 4:235–282, 1994.
G. Di Battista, A. Garg, G. Liotta, A. Parise, R. Tamassia, E. Tassinari, F. Vargiu, and L. Vismara. Drawing directed graphs: An experimental study. Technical Report CS-96-24, Center for Geometric Computing, Dept. Computer Science, Brown Univ., 1996. ftp://ftp.cs.brown.edu/pub/techreports/96/ cs96-24.ps.Z.
G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of three graph drawing algorithms. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 306–315, 1995.
G. Di Battista, A. Garg, G. Liotta, R. Tamassia, E. Tassinari, and F. Vargiu. An experimental comparison of four graph drawing algorithms. Comput. Geom. Theory Appl., 1996 (to appear). http://www.cs.brown.edu/cgc/papers/ dglttv-ecfgd-96.ps.gz.
G. Di Battista, E. Pietrosanti, R. Tamassia, and I. G. Tollis. Automatic layout of PERT diagrams with XPERT. In Proc. IEEE Workshop on Visual Languages (VL'89), pages 171–176, 1989.
G. Di Battista and R. Tamassia. Algorithms for plane representations of acyclic digraphs. Theoret. Comput. Sci., 61:175–198, 1988.
G. Di Battista, R. Tamassia, and I. G. Tollis. Area requirement and symmetry display of planar upward drawings. Discrete Comput. Geom., 7:381–401, 1992.
G. Di Battista, R. Tamassia, and I. G. Tollis. Constrained visibility representations of graphs. Inform. Process. Lett., 41:1–7, 1992.
E. R. Gansner, E. Koutsofios, S. C. North, and K. P. Vo. A technique for drawing directed graphs. IEEE Trans. Softw. Eng., 19:214–230, 1993.
E. R. Gansner, S. C. North, and K. P. Vo. DAG — A program that draws directed graphs. Softw. — Pract. Exp., 18(11):1047–1062, 1988.
A. Garg and R. Tamassia. Planar drawings and angular resolution: Algorithms and bounds. In J. van Leeuwen, editor, Algorithms (Proc. ESA '94), volume 855 of Lecture Notes in Computer Science, pages 12–23. Springer-Verlag, 1994.
A. Garg and R. Tamassia. Upward planarity testing. Order, 12:109–133, 1995.
M. Himsolt. Comparing and evaluating layout algorithms within GraphEd. J. Visual Lang. Comput., 6(3), 1995. (Special Issue on Graph Visualization, I. F. Cruz and P. Eades, editors).
S. Jones, P. Eades, A. Moran, N. Ward, G. Delott, and R. Tamassia. A note on planar graph drawing algorithms. Technical Report 216, Department of Computer Science, University of Queensland, 1991.
M. Jünger and P. Mutzel. Exact and heuristic algorithms for 2-layer straightline crossing minimization. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes in Computer Science, pages 337–348. Springer-Verlag, 1996.
E. Koutsofios and S. North. Drawing graphs with dot, 1993. dot user's manual. ftp://ftp.research.att.com/dist/drawdag/.
S. North. 5114 directed graphs, 1995. Manuscript. ftp://ftp.research.att.com/dist/drawdag/.
I. Rival. Reading, drawing, and order. In I. G. Rosenberg and G. Sabidussi, editors, Algebras and Orders, pages 359–404. Kluwer Academic Publishers, 1993.
K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. Syst. Man Cybern., SMC-11(2):109–125, 1981.
R. Tamassia and I. G. Tollis. A unified approach to visibility representations of planar graphs. Discrete Comput. Geom., 1(4):321–341, 1986.
R. Tamassia and I. G. Tollis. Planar grid embedding in linear time. IEEE Trans. Circuits Syst., CAS-36(9):1230–1234, 1989.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1997 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Di Battista, G. et al. (1997). Drawing directed acyclic graphs: An experimental study. In: North, S. (eds) Graph Drawing. GD 1996. Lecture Notes in Computer Science, vol 1190. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62495-3_39
Download citation
DOI: https://doi.org/10.1007/3-540-62495-3_39
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62495-0
Online ISBN: 978-3-540-68048-2
eBook Packages: Springer Book Archive