Minimum Depth Graph Embeddings and Quality of the Drawings: an Experimental Analysis

Pizzonia, Maurizio (2006) Minimum Depth Graph Embeddings and Quality of the Drawings: an Experimental Analysis. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 397-408 (Official URL: http://dx.doi.org/10.1007/11618058_36).

Full text not available from this repository.

Abstract

The depth of a planar embedding of a graph is a measure of the topological nesting of the biconnected components of the graph in that embedding. Motivated by the intuition that lower depth values lead to better drawings, previous works proposed efficient algorithms for finding embeddings with minimum depth. We present an experimental study that shows the impact of embedding depth minimization on important aesthetic criteria and relates the effectiveness of this approach with measures of how much the graph resembles a tree or a biconnected graph. In our study, we use a well known test suite of graphs obtained from real-world applications and a randomly generated one with favorable biconnectivity properties. In the experiments we consider orthogonal drawings computed using the topology-shape-metrics approach.

Item Type:Conference Paper
Additional Information:10.1007/11618058_36
Classifications:G Algorithms and Complexity > G.490 Embeddings
D Aesthetics > D.999 Others
ID Code:721

Repository Staff Only: item control page

References

A. Alberts, C. Gutwenger, P. Mutzel, and S. Näher. AGD-Library: A library of algorithms for graph drawing. In Proc. Workshop on Algorithm Engineering, pages 112-123, 1997.

G. Di Battista, W. Didimo, M. Patrignani, and M. Pizzonia. Orthogonal and quasi-upward drawings with vertices of prescribed size. In Graph Drawing (Proc. GD'99), volume 1731 of Lecture Notes Comput. Sci. Springer-Verlag, 1999.

P. Bertolazzi, G. Di Battista, amd W. Didimo. Computing orthogonal drawings with the minimum number of bends. In Workshop Algorithms Data Struct. (WADS'97), volume 1272 of Lecture Notes Comput. Sci., pages 331-344. Springer-Verlag, 1997.

P. Bertolazzi, G. Di Battista, amd W. Didimo. Computing orthogonal drawings with the minimum number of bends. IEEETC: IEEE Transactions on Computers, 49, 2000.

D. Bienstock and C. L. Monma. On the complexity of embedding planar graphs to minimize certain distance measures. Algorithmica, 5(1):93-109, 1990.

U. Brandes and D. Wagner. Dynamic grid embedding with few bends and changes. Lecture Notes in Computer Science, 1533, 1998.

Ulrik Brandes and Dorothea Wagner. A Bayesian paradigm for dynamic graph layout. In Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 236-247, Springer-Verlag, 1998.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, Upper Saddle River, NJ, 1999.

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., 7:303-325, 1997.

Giuseppe Di Battista et al. Graph Drawing Toolkit. University of Rome III, Italy. http://-www.dia.uniroma3.it/~gdt/.

W. Didimo and G. Liotta. Computing orthogonal drawings in a variable embedding setting. In Algorithms and Computation (Proc. ISAAC '98), volume 1533 of Lecture Notes Comput. Sci., pages 79-88. Springer-Verlag, 1998.

Ulrich Fößmeier and Michael Kaufmann. Drawing high degree graphs with low bend numbers. In Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes Comput. Sci., pages 254-266. Springer-Verlag, 1996.

M. R. Garey and D. S. Johnson. Crossing number is NP-complete. SIAM J. Algebraic Discrete Methods, 4(3):312-316, 1983.

C. Gutwenger and P. Mutzel. Graph embedding with minimum depth and maximum external face. In Graph Drawing (Proc. GD '03), volume 2912 of Lecture Notes Comput. Sci., pages 259-272. Springer-Verlag Heidelberg, 2004.

J. Hopcroft and R. E. Tarjan. Efficient planarity testing. J. ACM, 21(4):549-568, 1974.

M. Jünger and P. Mutzel. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica, 16(1):33-59, 1996.

Michael Jünger, Sebastian Leipert, and Petra Mutzel. Pitfalls of using PQ-Trees in automatic graph drawing. In Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 193-204. Springer-Verlag, 1997.

G. W. Klau and P. Mutzel. Optimal compaction of orthogonal grid drawings. In IPCO: 7th Integer Programming and Combinatorial Optimization Conference, volume 1610 of Lecture Notes Comput. Sci. Springer-Verlag, 1999.

Harald Lauer, Matthias Ettrich, and Klaus Soukup. GraVis - system demonstration. In Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 344-349. Springer-Verlag, 1997.

Maurizio Patrignani. On the complexity of orthogonal compaction. Computational Geometry: Theory and Applications, 19(1):47-67, 2001.

M. Pizzonia. Engineering of Graph Drawing Algorithms for Applications. PhD thesis, Dipartimento di Informatica e Sistemistica, University degli Studi "La Sapienza" di Roma, 2001.

M. Pizzonia and R. Tamassia. Minimum depth graph embedding. In M. Paterson, editor, Algorithms - ESA 2000, volume 1879 of Lecture Notes Comput. Sci. Springer-Verlag, 2000.

H. C. Purchase, R. F. Cohen, and M. James. Validating graph drawing aesthetics. In F. J. Brandenburg, editor, Graph Drawing (Proc. GD '95), volume 1027 of Lecture Notes Comput. Sci., pages 435-446. Springer-Verlag, 1996.

R. Tamassia. On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput., 16(3):421-444, 1987.