Online Hierarchical Graph Drawing

North, Stephen and Woodhull, Gordon (2002) Online Hierarchical Graph Drawing. In: Graph Drawing 9th International Symposium, GD 2001, September 23-26, 2001, Vienna, Austria , pp. 232-246 (Official URL:

Full text not available from this repository.


We propose a heuristic for dynamic hierarchical graph drawing. Applications include incremental graph browsing and editing, display of dynamic data structures and networks, and browsing large graphs. The heuristic is an on-line interpretation of the static layout algorithm of Sugiyama, Togawa and Toda. It incorporates topological and geometric information with the objective of making layout animations that are incrementally stable and readable through long editing sequences. We measured the performance of a prototype implementation.

Item Type:Conference Paper
Additional Information:10.1007/3-540-45848-4_19
Classifications:M Methods > M.500 Layered
G Algorithms and Complexity > G.700 Layering
M Methods > M.300 Dynamic / Incremental / Online
P Styles > P.480 Layered
ID Code:494

Repository Staff Only: item control page


Giuseppe Di Battista, Peter Eades, Roberto Tomassia, and Ioannis G. Tollis. Graph Drawing: algorithms for the visualization of graphs. Prentice-Hall, 1999.

Therese Bield and Michael Kaufmann. Area-efficient static and incremental graph drawings. In Proc. 5th European Symposium on algorithms (ESA '97), volume 1284 of Lecture Notes in Computer Science, pages 37-52. Springer-Verlag, 1997.

K. Bohringer and F. Newbery Pulisch. Using constraints to acieve stability in automatic graph layout algorithms. In Proceedings of ACM CHI'90, pages 43-51, 1990.

S.S. Bridgeman, J. Fanto, A. Garg, R. Tamassia, and L. Vismara. Interactive Giotto: An algorithm for interactive orthogonal graph drawing. In G. Di Battista, editor, Graph Drawing '97, volume 1353 of Lecture Notes in Computer Science, pages 303-308, Rome, Italy, 1998. Springer-Verlag.

R. Schonfeld, C. Matuszewski and P. Molitor. Using sifting for k-layer crossing minimization. In Jan Kratochvíl, editor, Graph Drawing '99, volume 1971 of Lecture Notes in Computer Science, pages 217-224. Springer-Verlag.

J. Cohen. Drawing graphs to convey proximity: an incremental arrangement method. ACM Trans. on Computer-Human Interfaces, 4(11):197-229, 1997.

D. Dobkin, E. Gansner, E. Koutsofios, and S. North. Implementing a general purpose edge router. In G. Di Battista, editor, Graph Drawing '97, volume 1353 of Lecture

Notes in Computer Science,Rome, Italy, 1998. Springer-Verlag.

P. Eades and C. Friedrich. The Marey graph animation tool demo. In Joe Marks, editor, Graph Drawing '00, volume

1984 of Lecture Notes in Computer Science, pages 396-406. Springer-Verlag, 2001.

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

Peter Eades, Robert F. Cohen, and Mao Lin Huang. Online animated graph drawing for web navigation. In G. Di Battista, editor, Graph Drawing '97, volume 1353 of Lecture

Notes in Computer Science, Rome, Italy, 1998. Springer- Verlag.

J. Ellson and S. North. TclDG - a Tcl extension for dynamic graphs. In Proc. 4th USENIX Tcl/Tk Workshop, pages 37-48, 1996.

E. R. Gansner, E. Koutsofios, S.C. North, and K.-P. Vo. A technique for drawing directed graphs. IEEE Trans. Software Engineering, 19(3):214-230, 1993.

M. Huang and P. Eades. A fully animated interactive system for clustering and navigating huge graphs. In Sue H. Whitesides, editor, Graph Drawing '98, volume 1547 of Lecture Notes in Computer Science, pages 374-383, Montreal, Canada, 1999. Springer-Verlag.

Tamara Munzner. Interactive visualization of large graphs and networks. PhD thesis, Stanford University, 2000.

A. Papakostas, J. M. Six, and I. G. Tollis. Experimental and theoretical results in interactive orthogonal graph drawing. in S. C. North, editor, Graph Drawing '96, volume 1190 of Lecture Notes in Computer Science, pages 101-112, 1997.

K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical systems. IEEE Trans. on Systems, Man and Cybernetics, SMC-11(2):109-125, 1981.

G. Woodhull and S. North. Montage- an ActiveX container for dynamic interfaces. In Proc. 2nd USENIX Windows NT Symposium, 1998.