The main idea of the algorithm is to partition the nodes into layers and order the nodes within the layers such that edge crossings are reduced. 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].

**Figure 15:** Phases of Layer Layout Algorithm

Layer layout consists of four phases (Fig. 15):

- 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).

- Phase 1: Partitioning into layers
- Phase 2: Sorting of nodes
- Phase 3: Positioning of nodes
- Phase 4: Positioning of edges

Thu Aug 1 15:27:34 PDT 1996