Force-Directed Graph Layout
When to use a force-directed layout and how to configure it
A force-directed graph drawing algorithm - also known as spring-embedder or energy-based placement algorithm - arranges graphs in an organic and aesthetically pleasing way. The resulting diagrams often expose the inherent symmetric and clustered structure of a graph and show a well-balanced distribution of nodes with few edge crossings.
Force-directed graph layouts are commonly used in the following application areas: network visualization, large graph visualization, knowledge representation, system management, and mesh visualization.
How Does Force-Directed Layout Work?
The algorithm is based on a physical model. Nodes are represented as points in a plane that are electrically charged and apply repulsive forces against each other. Edges connect these points simulating a spring-force, attracting adjacent nodes. The model iteratively determines the resulting forces that act on the nodes and try to move the nodes closer to an equilibrium where all forces add up to zero, and the position of the nodes stays stable.
Popular implementations of this algorithm were published by Fruchtermann and Reingold, as well as Kamada and Kawai. The advantage of the algorithm lies in the simplicity of the implementation. More, it works rather well for most graphs where the number of edges is similar to the number of nodes. On the other hand, dense graphs with too many edges or very sparse graphs that barely have any structure tend not to work well. Also, if the directions of the edges are important, the visualization may not be the best choice because that information is not taken into account by the algorithm at all.
Organic Layout - the Force-Directed Layout Algorithm of yFiles
Automatic layout algorithms are one of the key features of the commercial programming library yFiles.
yFiles provides a very sophisticated implementation of the force-directed graph layout algorithm called Organic Layout that is well suited for both small and large graphs and can easily be configured. It can avoid node/edge overlaps and supports user-specified node sizes and edge lengths.
Furthermore, it supports the following advanced features that go far beyond that provided by basic implementations.
Incremental Layout
In an incremental layout, the algorithm places new elements on suitable positions without changing the position of the existing elements too much. This feature leads to drawing results that preserves the user’s mental map of the diagram. yFiles also provides an interactive version of the organic layout algorithm that calculates continuous updates for a changing diagram. Hence, combining the interactive algorithm with the incremental layout feature yields especially powerful visualizations.
The following application showcases the interactive and incremental force-directed layout: Fraud Detection Demo.
Highlight Specific Substructures
The algorithm is able to identify some predefined regular substructures like chains, stars, cycles, and parallel structures and arrange them in an optimized manner. As shown in the example below, this makes such structures easily recognizable.
Nested Graph Structures
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.
Partitioning Into Swimlanes or Grid-like Table Structures
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.
