Sugiyama scheme

Layered graph drawing or hierarchical graph drawing is a type of graph drawing in which the vertices of a directed graph are drawn in horizontal rows or layers with the edges generally directed downwards. It is also known as Sugiyama-style graph drawing after Kozo Sugiyama, who first developed this drawing style.

The ideal form for a layered drawing would be an upward planar drawing, in which all edges are oriented in a consistent direction and no pairs of edges cross. However, graphs often contain cycles, minimizing the number of inconsistently-oriented edges is NP-hard, and minimizing the number of crossings is also NP-hard, so layered graph drawing systems typically apply a sequence of heuristics that reduce these types of flaws in the drawing without guaranteeing to find a drawing with the minimum number of flaws.

The construction of a layered graph drawing proceeds in a sequences of steps:

In its simplest form, layered graph drawing algorithms may require O(mn) time in graphs with n vertices and m edges, because of the large number of dummy vertices that may be created. However, for some variants of the algorithm, it is possible to simulate the effect of the dummy vertices without actually constructing them explicitly, leading to a near-linear time implementation.

The "dot" tool in Graphviz produces layered drawings. A layered graph drawing algorithm is also included in Microsoft Automatic Graph Layout and in Tulip.

Although typically drawn with vertices in rows and edges proceeding from top to bottom, layered graph drawing algorithms may instead be drawn with vertices in columns and edges proceeding from left to right. The same algorithmic framework has also been applied to radial layouts in which the graphs are arranged in concentric circles around some starting node and to three-dimensional layered drawings of graphs.

In layered graph drawings with many long edges, edge clutter may be reduced by grouping sets of edges into bundles and routing them together through the same set of dummy vertices. Similarly, for drawings with many edges crossing between pairs of consecutive layers, the edges in maximal bipartite subgraphs may be grouped into confluent bundles.

...
Wikipedia