Layered graph drawing is a type of graph drawing

Graph drawing

Graph drawing is an area of mathematics and computer science combining methods from geometric graph theory and information visualization to derive two-dimensional depictions of graphs arising from applications such as social network analysis, cartography, and bioinformatics...

 in which the vertices

Vertex (graph theory)

In graph theory, a vertex or node is the fundamental unit out of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges , while a directed graph consists of a set of vertices and a set of arcs...

 of a directed graph

Directed graph

A directed graph or digraph is a pair G= of:* a set V, whose elements are called vertices or nodes,...

 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

Kozo Sugiyama

was a Japanese computer scientist and graph drawing researcher.-Biography:Sugiyama was born on September 17, 1945 in Gifu Prefecture, Japan.He did both his undergraduate and graduate studies at Nagoya University, earning a doctorate in 1974. He then worked for Fujitsu until 1997, when he became a...

, who first developed this drawing style.

Layout algorithm

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

• If the input graph is not already a directed acyclic graph
  Directed acyclic graph
  In mathematics and computer science, a directed acyclic graph , is a directed graph with no directed cycles. That is, it is formed by a collection of vertices and directed edges, each edge connecting one vertex to another, such that there is no way to start at some vertex v and follow a sequence of...
  
  , a set of edges is identified the reversal of which will make it acyclic. Finding the smallest possible set of edges is the NP-complete
  NP-complete
  In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
  
   feedback arc set
  Feedback arc set
  In graph theory, a directed graph may contain directed cycles, a one-way loop of edges. In some applications, such cycles are undesirable, and we wish to eliminate them and obtain a directed acyclic graph . One way to do this is simply to drop edges from the graph to break the cycles...
  
   problem, so often greedy heuristics
  Greedy algorithm
  A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
  
   are used here in place of exact optimization algorithms. Alternatively, if the number of reversed edges is very small, these edges can be found by a fixed-parameter-tractable algorithm
  Parameterized complexity
  Parameterized complexity is a branch of computational complexity theory in computer science that focuses on classifying computational problems according to their inherent difficulty with respect to multiple parameters of the input. The complexity of a problem is then measured as a function in those...
  
  .
• The vertices of the directed acyclic graph resulting from the first step are assigned to layers, such that each edge goes from a higher layer to a lower layer. The goals of this stage are to simultaneously produce a small number of layers, few edges that span large numbers of layers, and a balanced assignment of vertices to layers. For instance, assigning vertices by layers according to the length of the longest path starting from each vertex produces an assignment with the minimum possible number of layers. The Coffman–Graham algorithm
  Coffman–Graham algorithm
  In job shop scheduling and graph drawing, the Coffman–Graham algorithm is an algorithm, named after Edward G. Coffman, Jr. and Ronald Graham, for arranging the elements of a partially ordered set into a sequence of levels...
  
   may be used to find a layering with a predetermined limit on the number of vertices per layer, approximating the minimum possible number of layers. Alternatively, the problem of minimizing the total number of layers spanned by the edges (without any limits on the number of vertices per layer) may be solved using linear programming
  Linear programming
  Linear programming is a mathematical method for determining a way to achieve the best outcome in a given mathematical model for some list of requirements represented as linear relationships...
  
  . Integer programming
  Integer programming
  An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers. In many settings the term refers to integer linear programming, which is also known as mixed integer programming.Integer programming is NP-hard...
  
   procedures, although more time-consuming, may be used to combine edge length minimization with limits on the number of vertices per level.
• Edges that span multiple layers are replaced by paths of dummy vertices so that, after this step, each edge in the expanded graph connects two vertices on adjacent layers of the drawing.
• The vertices within each layer are permuted
  Permutation
  In mathematics, the notion of permutation is used with several slightly different meanings, all related to the act of permuting objects or values. Informally, a permutation of a set of objects is an arrangement of those objects into a particular order...
  
   in an attempt to reduce the number of crossings among the edges connecting it to the previous layer. Finding the minimum number of crossings or finding a maximum crossing-free set of edges is NP-complete, even when ordering a single layer at a time in this way, so again it is typical to resort to heuristics, such as placing each vertex at a position determined by finding the average or median of the positions of its neighbors on the previous level and then swapping adjacent pairs as long as that improves the number of crossings.
• Each vertex is assigned a coordinate within its layer, consistent with the permutation calculated in the previous step.
• The edges reversed in the first step of the algorithm are returned to their original orientations, the dummy vertices are removed from the graph and the vertices and edges are drawn. To avoid intersections between vertices and edges, edges that span multiple layers of the drawing may be drawn as polygonal chains or spline curves passing through each of the positions assigned to the dummy vertices along the edge.

Implementations

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

Graphviz

Graphviz is a package of open-source tools initiated by AT&T Labs Research for drawing graphs specified in DOT language scripts. It also provides libraries for software applications to use the tools...

 produces layered drawings. A layered graph drawing algorithm is also included in Microsoft Automatic Graph Layout

Microsoft Automatic Graph Layout

Microsoft Automatic Graph Layout is a .NET library for automatic graph layout.It was created by Lev Nachmanson at Microsoft Research.Earlier versions carried the name GLEE .- Contents :...

 and in Tulip

Tulip (software)

Tulip is an information visualization framework dedicated to the analysis and visualization of relational data. Tulip aims to provide the developer with a complete library, supporting the design of interactive information visualization applications for relational data that can be tailored to the...

.

Variations

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.

Drawings in which the vertices are arranged in layers may be constructed by algorithms that do not follow Sugiyama's framework. For instance, it is possible to tell whether an undirected graph has a drawing with at most k crossings, using h layers, in an amount of time that is polynomial for any fixed choice of k and h, using the fact that the graphs that have drawings of this type have bounded pathwidth.

For layered drawings of concept lattices, a hybrid approach combining Sugiyama's framework with additive methods (in which each vertex represents a set and the position of the vertex is a sum of vectors representing elements in the set) may be used. In this hybrid approach, the vertex permutation and coordinate assignment phases of the algorithm are replaced by a single phase in which the horizontal position of each vertex is chosen as a sum of scalars representing the elements for that vertex.
Layered graph drawing methods have also been used to provide an initial placement for force-directed graph drawing algorithms.