Layout of Compound Graphs

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

(4) 		 od 

(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. The advantages: (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 are recalculated. 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. [STT81, EaSu90]:

1. 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 [SuMi91]; 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.
2. Calculate levels for the nodes and frame borders by sorting R topologically. If R is cyclic, some primitive edges are removed until R is acyclic. This is very similar to the partitioning phase of the normal hierarchical layout algorithm.
3. Normalize the representation. Edges crossing several levels are split into short edges and dummy nodes. 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.
4. 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 method.
5. 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.