There are several common layout methods for compound graphs.
The recursive method is mostly used [PaTi90, No93, He92, MMPH96, Sa96b]:
(1) traversing the nesting tree T in postorder, for each do
(2) layout graph consisting of the children of f in T
(3) compute bounding box of f
(5) layout unnested nodes
The layout of each frame f is calculated independently.
For the layout of the surrounding frame, f is considered as a large node.
(1) It is very simple to implement.
(2) Each frame can use a specific layout algorithm.
(3) If there is a change in frame f, it is not necessary to recalculate
a complete layout. Only the frames on the path in T from the root to f
The disadvantage: edges between nodes of different frames are not positioned
properly, since the position of a node is calculated only with respect
to the frame it belongs to.
The nondividing method [SuMi91, Sa96b] is more complex:
It applies a layout method at once to all frames, and thus it is able
to deal properly with edges crossing frames.
It is a variant of the hierarchical layout algorithm by Sugiyama e.a.
Calculate a flat representation R of the compound graph.
The flat representation is used to calculate the levels of the
nodes such that most edges point downwards.
It contains representatives of all nodes V and frames F.
A frame represents the upper border of the frame
we can also add a second instance f' of f to R that represents
the lower border [Sa96b].
A node v of a frame f must be positioned in between the
borders f and f', which is represented by edges .
A primitive edge e has an instance in R as it requires
different levels of source and target nodes.
Calculate levels for the nodes and frame borders by
sorting R topologically.
If R is cyclic, some primitive edges are removed until R
This is very similar to the partitioning phase of the normal
hierarchical layout algorithm.
Normalize the representation.
Edges crossing several levels are split into short edges and dummy
For the dummy nodes, it must be decided which frame they belong to.
Thus, [SuMi91] propose a proper compound digraph representation
where nested frames are used instead of dummy nodes.
[Sa96b] uses a simple heuristics by inspecting the frames of the
start and end node of the edge.
At each level, permute the nodes in order to reduce edge crossings.
This gives the relative position of the node.
It is important that (a) all nodes belonging to a frame are in a
consecutive sequence in the permutation,
(b) the frames are not intertwined, i.e. the relative order
of the frames is the same on all levels they occur.
The crossing reduction is a recursive variant of the barycenter
Finally, calculate absolute positions of nodes and frames.
Nodes of the same frame should be placed close together with
a distance to the nodes of the other frames, such that a
surrounding rectangle can be drawn.
[Sa96b] uses a variant of the pendulum method in this step.
The advantage of this method: the layout shows the compound
graph properly without overlappings.
If there are edges from the outside of a frame to an inner node, then
the placement of the node is not only influenced by the situation in the
frame, but also by the global situation.
The disadvantages: (1) It is relatively slow compared to the
recursive divide-and-conquer method.
(2) Every local change causes a global relayout.
(3) Frames are not independent, thus all frames must be treated with
the same layout parameters.