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 , 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

Actions (login required)

View Item View Item