Graph Embedding with Minimum Depth and Maximum External Face (Extended Abstract)

Gutwenger, Carsten and Mutzel, Petra (2004) Graph Embedding with Minimum Depth and Maximum External Face (Extended Abstract). In: Graph Drawing 11th International Symposium, GD 2003, September 21-24, 2003, Perugia, Italy , pp. 259-272 (Official URL: http://dx.doi.org/10.1007/978-3-540-24595-7_24).

Full text not available from this repository.

Abstract

We present new linear time algorithms using the SPQR-tree data structure for computing planar embeddings of planar graphs optimizing certain distance measures. Experience with orthogonal drawings generated by the topology-shape-metrics approach shows that planar embeddings following these distance measures lead to improved quality of the final drawing in terms of bends, edge length, and drawing area. Given a planar graph, the algorithms compute the planar embedding with 1. the minimum depth among the set of all planar embeddings of G, 2. the external face of maximum size among the set of all planar embeddings of G, 3. the external face of maximum size among the set of all embeddings of G with minimum depth.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-24595-7_24
Classifications:M Methods > M.800 Topology-shape-metrics
M Methods > M.600 Planar
G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.560 Geometry
ID Code:456

Repository Staff Only: item control page

References

C. Batini, E. Nardelli, and R. Tamassia. A layout algorithm for data-flow diagrams. IEEE Trans. Soft. Eng., SE-12(4):538-546, 1986.

C. Batini, M. Talamo, and R. Tamassia. Computer aided layout of entity relationship diagrams. The Journal of Systems and Software, 4:163-173, 1984.

C. Batini, M. Talamo, and R. Tamassia. Computer aided layout of entity relationship diagrams. The Journal of Systems and Software, 4:163-173, 1984.

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

N. Chiba, T. Nishizeki, S. Abe, and T. Ozawa. A linear algorithm for embedding planar graphs using PQ-trees. J. Computer and System Science, 30:54-76, 1985.

G. Di Battista, P. Eades, R. Tamassia, and I. G. Tollis. Graph Drawing. Prentice Hall, 1998.

G. Di Battista and R. Tamassia. On-line maintenance of triconnected components with SPQR-trees. Algorithmica, 15:302-318, 1996.

G. Di Battista and R. Tamassia. On-line planarity testing. SIAM J. Comput., 25(5):956-997, 1996.

Didimo and Liotta. Computing orthogonal drawings in a variable embedding setting. In K. Chwa, editor, Algorithms and Computation (Proc. ISAAC '98), volume 1533 of LNCS, pages 79-88. Springer-Verlag, 1998.

A. Garg and R. Tamassia. On the computational complexity of upward and rectilinear planarity testing. SIAM J. Computing, 31(2):601-625, 2002.

Graph drawing toolkit: An object-oriented library for handling and drawing graphs. http://www.dia.uniroma3.it/gdt.

C. Gutwenger and P. Mutzel. A linear time implementation of SPQR trees. In J. Marks, editor, Graph Drawing (Proc. GD 2000), volume 1984 of LNCS, pages 77-90. Springer-Verlag, 2001.

G. Liotta, F. Vargiu, and G. Di Battista. Orthogonal drawings with the minimum number of bends. In Proceedings of the 6th Canadian Conference on Computational Geometry, pages 281-286. University of Saskatchewan, 1994.

K. Mehlhorn and P. Mutzel. On the embedding phase of the Hopcoft and Tarjan planarity testing algorithm. Algorithmica, 16(2):233-242, 1996.

P. Mutzel and R. Weiskircher. Bend minimization in orthogonal drawings using integer programming. In O. H. Ibarra and L. Zhang, editors, Proceedings of the Eight Annual International Conference on Computing and Combinatorics (COCOON 2002), volume 2387 of LNCS, pages 484-493. Springer-Verlag, 2002.

M. Pizzonia and R. Tamassia. Minimum depth graph embedding. In M. Paterson, editor, Algorithms - ESA 2000, volume 1879 of LNCS, pages 356-367. Springer-Verlag, 2000.

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

R. Tamassia, G. Di Battista, and C. Batini. Automatic graph drawing and readability of diagrams. IEEE Trans. Syst. Man Cybern., SMC-18(1):61-79, 1988.

R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146-160, 1972.

R. Weiskircher. New Applications of SPQR-Trees in Graph Drawing. PhD thesis, Universität des Saarlandes, 2002.