Visual Navigation of Compound Graphs

Raitner, Marcus (2004) Visual Navigation of Compound Graphs. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 403-413 (Official URL:

Full text not available from this repository.


This paper describes a local update scheme for the algorithm of Sugiyama and Misue (IEEE Trans. on Systems, Man, and Cybernetics 21 (1991) 876–892) for drawing views of compound graphs. A view is an abstract representation of a compound graph; it is generated by contracting subgraphs into meta nodes. Starting with an initial view, the underlying compound graph is explored by repeatedly expanding or contracting meta nodes. The novelty is a totally local update scheme of the algorithm of Sugiyama and Misue. It is more efficient than redrawing the graph entirely, because the expensive steps of the algorithm, e. g., level assignment or crossing minimization, are restricted to the modified part of the compound graph. Also, the locality of the updates preserves the userrsquos mental map: nodes not affected by the expand or contract operation keep their levels and their relative order; expanded edges take the same course as the corresponding contracted edge.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_41
Classifications:M Methods > M.300 Dynamic / Incremental / Online
P Styles > P.240 Compound
ID Code:611

Repository Staff Only: item control page


Sugiyama, K., Misue, K.: Visualization of structural Information: Automatic drawing of compound digraphs. IEEE Trans. on Systems, Man, and Cybernetics 21 (1991) 876-892

Eades, P., Feng, Q.W.: Multilevel visualization of clustered graphs. In: Proc. 4th GD. Vol. 1190 of LNCS. (1996) 101-112

Buchsbaum, A.L., Westbrook, J.R.: Maintaining hierarchical graph views. In: Proc. 11th SODA. (2000) 566-575

Raitner, M.: Dynamic tree cross products. In: Proc. 15th ISAAC. LNCS. (2004)

Misue, K., Eades, P., Lai, W., Sugiyama, K.: Layout adjustment and the mental map. Journal of Visual Languages and Computing 6 (1995) 183-210

Sander, G.: Graph layout for applications in compiler construction. TCS 217 (1999) 175-214

Branke, J.: Dynamic graph drawing. In Kaufmann, M., Wagner, D., eds.: Drawing Graphs - Methods and Models. Vol. 2025 of LNCS. Springer (2001) 228-246

North, S.C., Woodhull, G.: Online hierarchical graph drawing. In: Proc. 9th GD. Vol. 2265 of LNCS. (2001) 232-246

Schieh, F.S., McCreary, C.L.: Clan-based incremental drawing. In: Proc. 8th GD. Vol. 1984 of LNCS. (2000) 384-395

Huang, M.L., Eades, P.: A fully animated interactive system for clustering and navigating huge graphs. In: Proc. 6th GD. Vol. 1547 of LNCS. (1998) 374-383

Abello, J., Korn, J.: MGV: A system for visualizing massive multigraphs. IEEE Trans. on Visualization and Computer Graphics 8 (2002) 21-38

Buchsbaum, A.L., Goodrich, M.T., Westbrook, J.R.: Range searching over tree cross products. In: Proc. 8th ESA. Vol. 1879 of LNCS. (2000) 120-131

Raitner, M.: HGV: A library for hierarchies, graphs, and views. In: Proc. 10th GD. Vol. 1528 of LNCS. (2002) 236-243