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.

Thu Aug 1 15:27:34 PDT 1996