Drawing Graphs using Modular Decomposition

Papadopoulos, Charis and Voglis, Constantinos (2006) Drawing Graphs using Modular Decomposition. In: Graph Drawing 13th International Symposium, GD 2005, September 12-14, 2005, Limerick, Ireland , pp. 343-354 (Official URL: http://dx.doi.org/10.1007/11618058_31).

Full text not available from this repository.

Abstract

In this paper we present an algorithm for drawing an undirected graph G which takes advantage of the structure of the modular decomposition tree of G. Specifically, our algorithm works by traversing the modular decomposition tree of the input graph G on n vertices and m edges, in a bottom-up fashion until it reaches the root of the tree, while at the same time intermediate drawings are computed. In order to achieve aesthetically pleasing results, we use grid and circular placement techniques, and utilize an appropriate modification of a well-known spring embedder algorithm. It turns out, that for some classes of graphs, our algorithm runs in O(n+m) time, while in general, the running time is bounded in terms of the processing time of the spring embedder algorithm. The result is a drawing that reveals the structure of the graph G and preserves certain aesthetic criteria.

Item Type:Conference Paper
Additional Information:10.1007/11618058_31
Classifications:M Methods > M.400 Force-directed / Energy-based
P Styles > P.720 Straight-line
P Styles > P.120 Circular
ID Code:703

Repository Staff Only: item control page

References

G. Di Battista, P. Eades, R. Tamassia, and I.G. Tollis: Algorithms for the Visualization of Graphs, Prentice-Hall, 1999.

P. Bertolazzi, G. Di Battista, C. Mannino, and R. Tamassia: Optimal upward planarity testing of single-source digraphs, SIAM J. Comput., 27 (1998) 132-169.

U. Brandes, M. Eiglsperger, I. Herman, M. Himsolt, and M.S. Marshall: GraphML progress report: structural layer proposal, Proc. 9th Int. Symp. Graph Drawing (GD'01), LNCS 2265 (2001) 501-512.

A. Brandstädt, V.B.Le, and J.P. Spinrad: Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, 1999.

E. Dahlhaus, J. Gustedt, and R.M. McConnell: Efficient and practical algorithms for sequential modular decomposition, J. Algorithms, 41 (2001) 360-387.

P. Eades and Q.W Feng: Drawing clustered graphs on an orthogonal grid. Proc. 5th Int. Symp. Graph Drawing (GD'97), LNCS 1353 (1997) 146-157.

P. Eades, Q.W. Feng, and X Lin: Straight-line drawing algorithms for hierarchical graphs and clustered graphs, Proc. 4th Int. Symp. Graph Drawing (GD'96), LNCS 1190 (1996) 113-128.

Q.W. Feng, R.F. Cohen, and P. Eades: Planarity for clustered graphs. Proc. 3rd European Symp. Algorithms (ESA'95), LNCS 979 (1995) 213-226.

T. Fruchterman and E. Reingold: Graph drawing by force-directed placement, Software-Practice and Experience, 21 (1991) 1129-1164.

J. Gagneur, R. Krause, T. Bouwmeester, and G. Casari: Modular decomposition of protein-protein interaction networks, Genome Biology 5:R57 (2004).

E.R. Gansner and S.C. North: Improved force-directed layouts, Proc. 6th Int. Symp. Graph Drawing (GD'98), LNCS 1547 (1998) 364-373.

D. Harel and Y. Koren: Drawing graphs with non-uniform vertices, Proc. of Working Conference on Advanced Visual Interfaces (AVI'02), ACM Press 2002, 157-166.

M.L. Huang and P. Eades: A fully animated interactive system for clustering and navigating huge graphs, Proc. 6th Int. Symp. Graph Drawing (GD'98), LNCS 1547 (1998) 374-383.

W. Li, P. Eades, and N. Nikolov: Using spring algorithms to remove node overlapping, Proc. Asia Pacific Symp. Information Visualization (APVIS'05), 2005.

R.M. McConnell and J. Spinrad: Modular decomposition and transitive orientation, Discrete Math. 201 (1999) 189-241.

yEd - Java Graph Editor, http://www.yworks.com/en/products_yed_about.htm

C. Walshaw: A multilevel algorithm for force-directed graph drawing, J. Graph Algorithms Appl. 7 (2003) 253-285.

X. Wang and I. Miyamoto: Generating customized layouts, Proc. 3rd Int. Symp. Graph Drawing (GD'95), LNCS 1027 (1995) 504-515.