Phase 1: Partitioning into layers next up previous
Next: Phase 2: Sorting of Up: Layout Phases Previous: Layout Phases

Phase 1: Partitioning into layers

For each node v, a rank R(v) has to be calculated, that specifies the number of the layer that v belongs to. Layer 1 is the topmost layer. The span of an edge is S(v,w) = R(w) - R(v). In a directed graph, it might be required that most edges point downwards, i.e. that the spans are positive. However, it is tex2html_wrap_inline2478 -complete to find the minimal number of edges that cannot point downwards in a graph which contains cycles [GaJo79]. There are many heuristics for calculation of the rank (some more are described in [EaSu90]):

As mentioned above, some heuristics can only cope with acyclic graphs. Graphs with cycles have to be made acyclic first by (conceptually) reversing some edges. A heuristic to find these edges works as follows: Calculate the strongly connected components of the graph [Me84] in time O( |V| + |E| ). In each component C that contains more than one node, reverse an edge. Now try again to calculate the strongly connected components. Continue this loop, until each component has only one element. At the end, the converted graph will be acyclic. A good heuristic to find the edges to be reversed is to look for edges (v,w) where outdeg(v) is minimal but indeg(v) and indeg(w) are maximal.

This method can be implemented by recursion. In practice, it very often finds the minimal number of edges that must be reversed, although it is only a heuristic. However, it has the high time complexity O( r (|V| + |E|)) where r is the number of reversed edges.

Each ranking induces a hierarchy. In order to proceed, a proper hierarchy is needed, i.e. all edges must have span S(e) = 1. Thus, edges (v,w) with S(v,w) < 0 are reversed, i.e. replaced by edges (w,v). Then edges with S(v,w) = n > 1 are split into dummy nodes tex2html_wrap_inline2564 with tex2html_wrap_inline2566 and smaller edges tex2html_wrap_inline2568 , and edges with S(v,w) = 0 are diverted in a similar way. Edge splittings and reversions are always done only conceptually. The resulting edges are marked such that we can later draw one arrowheads at the appropriate position.


next up previous
Next: Phase 2: Sorting of Up: Layout Phases Previous: Layout Phases

Georg Sander
Thu Aug 1 15:27:34 PDT 1996