Planarization of Clustered Graphs (Extended Abstract)

Di Battista, Giuseppe and Didimo, Walter and Marcandalli, A. (2002) Planarization of Clustered Graphs (Extended Abstract). In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 60-74 (Official URL: http://dx.doi.org/10.1007/3-540-45848-4_5).

Full text not available from this repository.

Abstract

We propose a planarization algorithm for clustered graphs and experimentally test its efficiency and effectiveness. Further, we integrate our planarization strategy into a complete topology-shape-metrics algorithm for drawing clustered graphs in the orthogonal drawing convention.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_5
Classifications:M Methods > M.800 Topology-shape-metrics
P Styles > P.180 Cluster
G Algorithms and Complexity > G.840 Planarization
G Algorithms and Complexity > G.420 Crossings
P Styles > P.600 Poly-line > P.600.700 Orthogonal
ID Code:404

Repository Staff Only: item control page

References

AGD. A library of algorithms for graph drawing. Online. http://www.mpi-sb.mpg.de/AGD/.

P. Bertolazzi, G. Di Battista, and W. Didimo. Computing orthogonal drawings with the minimum number of bends. IEEE Transactions on Computers, 49(8), 2000.

U. Brandes, S. Cornelsen, and D. Wagner. How to draw the minimum cuts of a planar graph. In J. Marks, editor, Graph Drawing (Proc. GD '00), volume 1984 of Lecture Notes Comput. Sci., pages 103-114. Springer-Verlag, 2000.

G. Di Battista, W. Didimo, M. Patrignani, and M. Pizzonia. Orthogonal and quasi-upward drawings with vertices of arbitrary size. In Proc. GD '99, volume 1731 of LNCS, pages 297-310, 2000.

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.

H.N. Djidjev. A linear algorithm for the maximal planar subgraph problem. In Proc. 4th Workshop Algorithms Data Struct., Lecture Notes Comput. Sci. Springer-Verlag, 1995.

C.A. Duncan, M.T. Goodrich, and S.G. Kobourov. Planarity-preserving clustering and embedding for large planar graphs. In J. Kratochvíl, editor, Graph Drawing (Proc. GD '99), volume 1731 of Lecture Notes in Comput. Sci., pages 186-196. Springer-Verlag, 1999.

P. Eades and Q.W. Feng. Multilevel visualization of clustered graphs. In S. North, editor, Graph Drawing (Proc. GD '96), volume 1190 of Lecture Notes Comput. Sci., pages 101-112. Springer-Verlag, 1996.

P. Eades, Q.W. Feng, and X. Lin. Straight line drawing algortihms for hierarchical graphs. In S. North, editor, Graph Drawing (Proc. GD '96), volume 1190 of Lecture Notes Comput. Sci., pages 113-128. Springer-Verlag, 1996.

P. Eades, Q.W. Feng, and H. Nagamochi. Drawing clustered graphs on an orthogonal grid. Journal of Graph Algorithms and Applications, 3(4):3-29, 2000.

S. Even. Graph Algorithms. Computer Science Press, Potomac, Maryland, 1979.

Q.W. Feng, R. Cohen, and P. Eades. How to draw a planar clustered graph. In Computing and Combinatorics (Cocoon '95), volume 959 of Lecture Notes Comput. Sci., pages 21-30. Springer-Verlag, 1995.

Q.W. Feng, R.F. Cohen, and P. Eades. Planarity for clustered graphs. In P. Spirakis, editor, Symposium on Algorithms (Proc. ESA '95), volume 979 of Lecture Notes Comput. Sci., pages 213-226. Springer-Verlag, 1995.

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

GDToolkit. Graph drawing toolkit. Online. http://www.dia.uniroma3.it/~gdt.

M.L. Huang and P. Eades. A fully animated interactive system for clustering and navigating huge graphs. In S.H. Whitesides, editor, Graph Drawing (Proc. GD '98), volume 1547 of Lecture Notes Comput. Sci., pages 374-383. Springer-Verlag, 1998.

M. Jünger, E.K. Lee, P. Mutzel, and T. Odenthal. A polyhedral approach to the multi-layer crossing number problem. In G. Di Battista, editor, Graph Drawing (Proc. GD '97), volume 1353 of Lecture Notes Comput. Sci., pages 13-24. Springer-Verlag, 1997.

M. Jünger and P. Mutzel. Maximum planar subgraphs and nice embeddings: Practical layout tools. Algorithmica, 16(1):33-59, 1996. (special issue on Graph Drawing, edited by G. Di Battista and R. Tamassia).

D. Lütke-Hüttman. Knickminimales Zeichen 4-planarer Clustergraphen. Master's thesis, Universität des Saarlandes, 1999.

T. Nishizeki and N. Chiba. Planar graphs: Theory and algorithms. Ann. Discrete Math., 32, 1988.

B. Shieber and U. Vishkin. On finding lowest common ancestors: Simplification and parallelization. SIAM J. Comput., 17(6):1253-1262, 1988.

K. Sugiyama and K. Misue. Visualization of structural information: Automatic drawing of compound digraphs. IEEE Trans. Softw. Eng., 21(4):876-892,1991.

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.