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]):
in topological order of the nodes. This results in a partitioning where all edges will point downwards in time complexity O(|V| + |E|).
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.
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.