Layered Graph Layout
The features of layered layouts and how to make the best use of them
A layered graph drawing algorithm - also known as hierarchical layout or Sugiyama algorithm - places the nodes of a graph into horizontal layers (virtual horizontal lines) such that the edges, modeling the relationships, point in a uniform direction, e.g., downwards as in the example below.
This style is especially suitable for applications where the direction of the relationships matters like diagrams showing ordered sequences of events or actions. Here, layered drawings help to emphasize the flow direction and, thus, to quickly get insight into the hierarchic relationships of elements.
Layered graph layouts are commonly used in the following application areas: workflow visualization, call graph visualization, entity-relationship diagrams, activity diagrams, biochemical/metabolic pathways, genealogical data, and network management.
The layered graph layout approach consists of three steps:
Layer assignment: the nodes are assigned to horizontal layers such that the edges point downwards.
Crossing reduction: the algorithm computes a sequence of the nodes within each layer, minimizing the number of crossings between edges.
Coordinate assignment: the nodes are assigned to coordinates maintaining the layers and sequence calculated in the previous steps.
yFiles is a commercial programming library designed explicitly for diagram visualization. The advanced layout algorithms of yFiles can comfortably transform the data in a readable, pleasing, and informative network. Its flagship algorithm is the layered layout or Hierarchic Layout Algorithm, as it is called there.
yFiles provides a very sophisticated implementation of the layered graph layout algorithm that supports a large number of advanced features and constraints. It is well suited for small and large graphs and can be easily configured.
In addition to the basic, traditional approach, it supports the following features.
In an incremental layout mode, the algorithm places a subset of the elements on suitable positions without changing the locations of the other elements too much. A typical use-case scenario for this feature is adding new elements to an existing diagram while preserving the user’s mental map of the current drawing. The Incremental Hierarchical Layout Example provides more details and an opportunity to explore the incremental mode interactively.
Nested graphs allow grouping of related nodes, e.g., the packages in a UML diagram that may contain other packages or classes. In such diagrams, the algorithm places all classes and sub-packages of a package within a rectangular area. The other elements are placed outside of that area, as shown in the figure below. The following example application shows a nesting graph:
Placing labels without overlaps close to the associated element is essential to omit ambiguity. Furthermore, the user can specify advanced placement preferences, e.g., whether an edge label should be placed close to the source, the target, or center of the edge’s route.
Swimlanes subdivide the drawing area into vertical or horizontal stripes that represent logical areas like, e.g., organizational units in a business model. The algorithm places each node in the associated stripe and, thus, significantly improves recognition of such structures. Swimlanes often appear in Flowchart, UML, and BPMN diagrams and are especially useful to emphasize a logical or time flow in a drawing. yFiles also supports grid-like table structures that correspond to having vertical and horizontal swimlanes at the same time, see Partition Grid Example.
In a bus-like structure, edges have shared segments to improve the compactness of the edge visualization or to emphasize their common meaning. Examples are available here: Edge Grouping Example and Bus Structure Example.
The point where an edge connects to a node is referred to as "port". There are domain-specific applications that require that the algorithm places the port where an edge enters or leaves a node at a specific side or location, for example, considering the predefined pins of electronic components in an electric circuit diagram. Here, the algorithm ensures that the edges connect to the associated pin location.
Furthermore, it is configurable whether the edges will connect to an exact port location, to one of a set of port candidates, to a specified side of the node, or without any restrictions.
Besides the above references, the following example applications for the Hierarchic Layout are available:
yFiles comes with many more sophisticated and highly customizable graph layout algorithms.