What is a compound graph?

Answer 1

A Compound Graph is an extension of a standard graph.

Let G be a graph, G=(V,E) where V is a set of vertices and E is a set of edges, that is e = (v1, v2) in V2

A compound graph C is defined by a tree T=(V,F) where V is the same set as G and F are tree edges f=(v1,v2) in V2. C=(G,T) where G=(V,E) and T=(V,F)

Furthermore, C has two additional constraints:

e=(v1,v2) in E implies:

1) v1 is not on the path of v2 to the root of T AND

2) v2 is not on the path of v1 to the root of T.

Intuitively, T defines a hierarchy. All the vertices sharing the same parent in T are in the same "group". The constraints state that you cannot have an edge connecting a vertex to one of its parent in the hierarchy.