Directed Graphs Drawing by Clan-Based Decomposition

Shieh, Fwu-Shan and McCreary, Carolyn (1996) Directed Graphs Drawing by Clan-Based Decomposition. In: Symposium on Graph Drawing, GD 1995, September 20-22, 1995, Passau, Germany , pp. 472-482 (Official URL:

Full text not available from this repository.


This paper presents a system for automatically drawing directed graphs by using a graphanalysis that decomposes a graph into modules we call clans. Our system, CG (Clan-based Graph Drawing Tool), uses a unique clan-based graph decomposition to determine intrinsic subgraphs (clans) in the original graph and to produce a parse tree. The tree is given attributes that specify the node layout. CG then uses tree properties with the addition of "routing nodes" to route the edges. The objective of the system is to provide, automatically, an aesthetically pleasing visual layout for arbitrary directed graphs. Using the clan-based decomposition, CG's drawings are unique in several ways: (1) The node layout can be balanced both vertically and horizontally; (2) Nodes within a clan, a subgraph of nodes that have a common relationship with the rest of the nodes in the graph, are placed close to each other in the drawing; (3) Nodes are grouped according to a two-dimensional affinity rather than a single dimension such as level or rank [13]; (4) The users can contract a clan into a single node and later expand the node to show the subgraph in its original clan; and (5) Crossings reduction processing by clan-based graph decomposition is faster than Sugiyama, Tagawa, and Toda [20,21] barycentric ordering algorithm. In addition to the capabilities of the old drawing system [16], several features have been added: (1) The modified barycentric technique is used to reduce crossings. In the modified technique, the components of matrix representation are clans instead of nodes. The users can (2) specify a node's size, shape, and label, and a edge's label in the textual input file; (3) contract a clan (subgraph) into a single node; (4) extract a clan (subgraph) and hide the rest of the graph; and (5) save the drawing into a file in Postscript format.

Item Type:Conference Paper
Additional Information:10.1007/BFb0021831
Classifications:M Methods > M.999 Others
G Algorithms and Complexity > G.999 Others
G Algorithms and Complexity > G.420 Crossings
S Software and Systems > S.999 Others
P Styles > P.999 Others
ID Code:217

Repository Staff Only: item control page


K. Andrews, R. R. Henry, and W. K. Yamamoto, "Design and implementation of the UW illustrated compiler," Univ. Washington, Dep. of Computer Science, Tech. Rep. 88-03-07, Mar. 1988.

M. J. Carpano, "Automatic Display of Hierarchized Graphs for Computer Aided Decision Analysis", IEEE Trans. on System Nab and Cybernetics, Vol. SMC-10, No. 11, 705-715, 1980.

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

I. F. Cruz, and R. Tamassia, "How to Visualize a Graph: Specification and Algorithms, "Tutorial on Graph Drawing, available at, 1994.

A. Davis, B. Gardiner and M. Gardiner, 1941, Deep South, Chicago: U. of Chgo. Press.

G. Di Battista, P. Eades, R. Tamassia, I. Tollis, "Algorithms for Drawing Graphs: an Annotated Bibliography", June, 1994, available via ftp from wilma.cs.brown ( in file pub/papers/compgeo/gdbiblio.tex.Z.

P. Eades and D. Kelley, "Heuristics for drawing 2-layered graphs," Ars Combinatoria, Vol. 21-A, 89-98, 1986.

P. Eades and N. Wormland, "Edge Crossings in Drawings of Bipartite Graphs", Algorithmica, Vol. 11, No. 4, 379-403, April 1994.

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

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

L. C. Freeman and D. R. White, 1993, "Using Gaiois Lattices to Represent Network Data," in P. V. Marsden, ed., Sociological Methodology 1993, Oxford: Blackwell, 127-146.

E. R. Gansner, S. C. North, and K. P. Vo, "DAG - A Program that Draws Directed Graphs," Software - Practice and Experience, Vol. 18, No. 11, 1047-1062, Nov. 1988.

E. R. Gansner, E. Koutsofios, S. C. North, and K. P. Vo, "A Technique for Drawing directed Graphs," IEEE Transactions on Software Engineering, Vol. 19, No. 3, 214-230, 1993.

Koutsofios and S. North, "Drawing Graphs with dot", Dot User's Manual, AT&T Bell Labs, Murray Hill, N. J., 1994.

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.

E. B. Messinger, "Automatic Layout of Large Directed Graphs," Univ. of Washington, Ph.D. dissertation, 1988.

E. B. Messinger, L. A. Rowe, and R. R. Henry, "A Divide-and-Conquer Algorithm for the Automatic Layout of Large Directed Graphs," IEEE Trans. on Sys. Man, and Cyb., Vol. 21 No. 1, 1-12, 1991.

L. A. Rowe, M. Davis, E. Messinger, and C. Meyer, "A Browse for Directed Graphs," Software-Practice and Experience, Vol. 17(1), 61-76, January 1987.

K. Sugiyama, S. Tagawa, and M. Toda, "Effective Representation of Hierarchies," in Proc. IEEE Int. Conf. Cybernetics and Society, New York, Oct. 1979.

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.

R. Tamassia, G. D. Battista, and C. Batini, "Automatic Graph Drawing and Readability of Diagrams," IEEE Trans. on Sys. Man, and Cyb., Vol. 18, No. 1, 61-79, 1988.

J. N. Warfield, "Crossing Theory and Hierarchy Mapping," IEEE Trans. on Syst., Man, and Cybernetics, Vol. 7, No. 7, 505-523, Jul. 1977.