page 2  (9 pages) 1 3

CG is unique in several ways:
? The node layout is balanced both vertically and horizontally.
? Nodes within a clan are placed close to each other in the drawing.
? Nodes are grouped according to two-dimensional affinity.

Graph Parsing

The node layout is determined by the combination of (1) parsing of the graph into logically cohesive subgraphs and (2) defining layout attributes to apply to the resulting parse tree. The parse is based on simple graph productions, and the attributes produce a layout that can be specified by a particular application. The foundation for the parse comes from the theory of 2- structures[6.,7.].

Clan-based graph decomposition (CGD) is a parse of a directed acyclic graph (DAG) into a hierarchy of subgraphs. The subgraphs defined by our graph grammar and parse are called clans. Let G be a DAG. A subset X ? G is a clan iff for all x, y ? X and all z ? G - X, (a) z is an ancestor of x iff z is an ancestor of y, and (b) z is a descendant of x iff z is a descendant of y. An alternate description of a clan depicts it as a subset of nodes where every element not in the subset is related in the same way (i.e. ancestor, descendant or neither) to each member in the subset. Trivial clans include singleton sets and the entire graph.

A simple clan C with nodes n1 ... nk is classified as beloning to one of three types. It is (i)

independent if it is a union of disconnected nodes; or (ii) linear if for every pair of nodes ni, nj in C, ni is an ancestor of nj or nj is an ancestor of ni. (iii) primitive if neither (i) nor (ii) applies.

Simple independent clans are sets of isolated nodes. Simple linear clans are sequences of one or more nodes vi,vi+1,...,vj-1,vj where for i < k, vi is an ancestor of vk. Any DAG can be constructed

from these simple clans through a series of productions. Any DAG can be parsed into a tree of clans whose leaves are trivial clans (graph nodes) and whose internal tree nodes are complex clans built from their descendants. The parse tree is unique when maximal linear and maximal independent clans are identified at each step in the parse.

The concept of a quotient graph is important because it allows the classification of clans as linear, primitive or independent to be applied to complex clans. Let C be a clan and {C1,,...Ck}

a partition of C, where each Ci is a maximal proper subclan of C. The quotient graph of C,

denoted C/C1...Ck, is the graph with nodes C1,...,Ck. There is an edge from Ci to Cj in the quotient

graph precisely when there is an edge (x,y) of C with x ? Ci and y ? Cj . Every clan can be iden-

tified as linear, primitive or independent according to the classification of its quotient graph. For every transitively reduced digraph there is a unique decomposition into quotient graphs that are identified as linear, primitive or independent [12.]. The quotient graphs form a hierarchy we call the parse tree.

Spatial Analysis for Node Layout

The parse tree of the graph is used to provide the graph with geometric interpretations that define the visual layout. A bounding box with known dimensions is associated with each clan, and the nodes in the clan are assigned locations within the bounding box. Synthetic attributes are associated with the parse tree hierarchy to show the embedding and dimensions of the bounding