Layered layout

A layered graph layout algorithm is mostly employed for digraphs, when it would be useful to have all the edges point in the same direction.

Figure: A graph showing a layered layout, created with the Sugiyama heuristic, with the layers shown. The bends in the edges correspond to dummy nodes.

A heuristic for creating a layered graph was put forward in a paper by Sugiyama et al. in [8]. As a consequence a layered layout is often referred to as a Sugiyama layout. In order to achieve the goal of having all the directed edges point in the same direction, while maintaining minimum edge bends, and minimum edge crossings, the heuristic assigns vertices to layers (Fig ) and uses the presence of dummy nodes to connect vertices which have an edge spanning more than one layer, such as the edge between vertices 1 - 9 in the graph shown in Fig. . As the Sugiyama heuristic can only be applied to an acyclic graph, extensions to the Sugiyama heuristic prefix it by preprocessing the graph to remove cycles.