Drawing Directed Acyclic Graphs: An Experimantal Study

Di Battista, Giuseppe and Garg, Ashim and Liotta, Giuseppe and Parise, Armando and Tamassia, Roberto and Tassinari, Emanuele and Vargiu, Francesco and Vismara, Luca (1997) Drawing Directed Acyclic Graphs: An Experimantal Study. In: Symposium on Graph Drawing, GD '96, September 18-20, 1996, Berkeley, California, USA , pp. 76-91 (Official URL: http://dx.doi.org/10.1007/3-540-62495-3_39).

Full text not available from this repository.

Abstract

In this paper we consider the class of directed acyclic graphs (DAGs), and present the results of an experimetal 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.

Item Type:Conference Paper
Additional Information:10.1007/3-540-62495-3_39
Classifications:M Methods > M.001 General
P Styles > P.001 General
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.420 Crossings
G Algorithms and Complexity > G.210 Bends
ID Code:104

Repository Staff Only: item control page

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 LNCS, 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 of 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/cgs/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 graphs. 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 LNCS, 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 LNCS, pages 337-348. Springer-Verlag, 1996.

E. Koutsofios and S.C. 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.