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 -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]):

• If the graph is acyclic, sort it topologically and calculate

  

  in topological order of the nodes. This results in a partitioning where all edges will point downwards in time complexity O(|V| + |E|).

• If the graph is acyclic, solve the problem to minimize

  

  subject to (1) for each node v and (2) for each edge (v,w). This can be done by standard linear programming methods [GKN93]. Even an integer solution exists and can be obtained. This results in a downward partitioning with minimal number of edge spans, i.e. minimal number D of dummy nodes.

• Calculate R(v) by a depth first search or breath first search. This results in an arbitrary partitioning in time complexity O(|V| + |E|).
• Calculate the minimum cost spanning tree [Me84] on the undirected instance of the graph. This is useful if edges e have priorities p(e). We use the cost 1/p(e). The result is a partitioning where edges of high priority gave small spans. The layout will be wide but not deep. The time complexity is .
• If the edge orientation is not important, apply a spring embedder as described in the section before. It is sufficient to take only and into account. Instead of two-dimensional coordinates, calculate a one-dimensional coordinate R(v). This results in a ranking where edges tend to have the same absolute value of span.

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 with and smaller edges , 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.