The main idea of the algorithm is to partition the nodes into layers
and order the nodes within the layers such that edge crossings
Variants of this idea were first described in [Wa77, Ca80, STT81].
The method described here is mainly based on the algorithm by
Sugiyama e.a. [STT81, EaSu90].
Partitioning of nodes into layers.
The goal is to construct a proper hierarchy, i.e.
a partioning where edges may only occur between adjacent layers.
If this is not possible, long edges crossing several layers
must be split into sequences of short edges and dummy nodes
must be inserted appropriately.
Sorting the nodes (and dummy nodes) within a layer,
such that only few edge crossings exist.
This gives the relative positions of the nodes.
Positioning of nodes.
This gives the absolute coordinates of the nodes.
The goal is to find balanced positions without overlappings.
Positioning of edges.
Start and end points of edges are approximately given by the
node positions, because they must be adjacent to the borders
of the nodes.
However, bend points must be calculated
to avoid crossings through nodes, or control points
for certain edge styles (e.g. splines).