Clan-Based Incremental Drawing

Shieh, Fwu-Shan and McCreary, Carolyn (2001) Clan-Based Incremental Drawing. In: Graph Drawing 8th International Symposium, GD 2000, September 20–23, 2000, Colonial Williamsburg, VA, USA , pp. 384-396 (Official URL:

Full text not available from this repository.


The stability is an essential issue for incremental drawings. To allow stable updating, means to modify graph slightly (such as adding or deleting an edge or a node) without changing the layout dramatically from previous layout. In this paper, a method for achieving stable incremental directed graph layout by using clan-based graph decomposition is described. For a given directed graph, the clan-based decomposition generates a parse tree. The parse tree, which is used for layout, is also employed in locating changes and maintaining visual stability during incremental drawing. By using the generated parse tree, each incremental update can be done very efficiently.

Item Type:Conference Paper
Additional Information:10.1007/3-540-44541-2_36
Classifications:M Methods > M.999 Others
M Methods > M.300 Dynamic / Incremental / Online
G Algorithms and Complexity > G.999 Others
M Methods > M.900 Tree
ID Code:433

Repository Staff Only: item control page


J. H. Cross II and R. S. Dannelly, "Reverse Engineering Graphical Representations of X Source Code," International Journal of Software Engineering and Knowledge Engineering, Spring, 1996.

A. H. Deutz, A. Ehrenfeucht, G. Rozenberg, "Clans and regions in 2-structures", Theoretical Computer Science, 129, 207-262, 1994.

G. Di Battista, P. Eades. R. Tamassia, I. Tollis, "Algorithms for Drawing Graphs: an Annotated Bibliography", Computation Geometry: Theory and Applications, 4(5):235-282, 1994.

A. Ehrenfeucht and G. Rozenberg, "Theory of 2-Structures, Part I: Clans, Basic Subclasses, and Morphismus,"Theoretical Computer Science, Vol. 70, 277-303, 1990.

A. Ehrenfeucht and G. Rozenberg, "Theory of 2-Structures, Part II: Representation Through Labeled Trees Families,"Theoretical Computer Science, Vol. 70, 305-342, 1990.

M. Frohlich,"Incremental Graphout in Visualization System - daVinci," PhD thesis, Department of Computer Science, The University of Bremen, Germany, November 1997.

C. M. McCrary, R. O. Chapman, and F. S. Shieh, "Using Graph Paring for Automatic Graph Drawing", IEEE Trans. on Systems Man, and Cybernetics -- Part A: Systems and Humans, Vol. 28, No. 5, 545-561, 1998.

C. L. McCreary and A. Reed, "A Graph Parsing Algorithm and Implementation," Tech. Rpt. TR-93-04, Dept. of Comp. Sci and Eng., Auburn U. 1993.

C. McCreary, F. S. Shieh, and H. Gill, "CG: a Graph Drawing System Using Graph Grammar Parsing," Lecture Notes in Computer Science, Vol. 894, 270-273, Springer-Verlag, 1995.

S. C. North, "Incremental Layout in DynaDAG," Lecture Notes in Computer Science, Vol. 1027, 409-418, Springer-Verlag, 1996.

G. Sander, "Graph Drawing Tools and Related Work,"

F. S. Shieh, "Stability and Topology of Graph Drawing," Auburn University, Ph.D. dissertation, 2000.

F. S. Shieh, and C. L. McCreary, "Directed Graphs Drawing by Clan-based Decomposition," Lecture Notes in Computer Science, Vol. 1027, 472 - 482, Springer-Verlag, 1996.

Tom Sawyer, "Graph Toolkit".

K. Sugiyama, S. Tagawa and M. Toda, "Methods for Understanding of Hierarchical System Structures," IEEE Trans. on Sys. Man, and Cyb., SMC-11, 109-125, 1981.