We recently encountered (via infosthetics) a paper from Danny Holten and Jarke J. van Wijk that demonstrates an algorithm for creating beautiful graph visualizations. The original paper is Force-Directed Edge Bundling for Graph Visualization, published in 2009.
In computer science theory, a graph is a collection of nodes and the edges between them. Graphs are useful abstractions for describing transit networks, computer networks, and relationships among people (such as in a social network). Over the years mathematicians and theorists have discovered that there are hundreds of additional problem types that can be rewritten as graph theory problems. So, understanding and visualizing graphs is important for a large number of problem domains.
While there are many ways to represent a graph visually, the most intuitive is to draw a set of points (nodes) with lines (edges) connecting them. The goal, of course, is to make the visualization intuitive to understand for a human observer. The visualization should be functionally readable, aesthetically appealing, and ideally should allow an observer to glean interesting information about the graph’s structure. For larger graphs, several issues regarding visualization immediately present themselves. First, nodes must be laid out such that they to not interfere with one another. Edges should be drawn so that they can be distinguished from one another, with minimal crossing, but should also connect two nodes with the shortest line possible and minimal curvature. Node size and edge thickness become important, and either nodes or edges are connected to real-world space, they should be placed in some analogous fashion.
Holten and van Wijk have introduced several novel ideas to graph visualization theory. Their main contribution is the grouping of similar edges using a clustering technique. Edges become flexible springs that can attract and repel one another. While other researchers have proposed edge-bundling techniques, Holten and van Wijk’s algorithm uses a “self-organizing” approach that does not require additional information in the form of control hierarchies or meshes as did previously published algorithms. By transforming the edges into springs, they are able to leverage existing algorithmic techniques for modeling real world systems.
Each edge is modeled as a spring, and a number of control points are placed along each edge. Each control point on a spring-edge is compared with its corresponding control point on every other edge that interacts with this edge. A global spring constant is used to inform localized (edge-specific) spring constants, and this determines the “stiffness” of the resulting diagram. Over many iterations, each control point is moved slightly according to the sum of all forces acting upon it. As control points move, they inform subsequent iterations and alter the forces acting on other edges in the graph. The number of control points is increased for later iterations to provide greater edge smoothing.
The authors discovered that this basic algorithm resulted in too much bundling. They therefore introduce several edge-compatibility measures that are used to adjust the forces acting between any two control points. Edges should exhibit greater bundling tendencies if they:
- are parallel rather than perpendicular
- are of similar lengths
- are proximate in space
- have similar “bands of sight” (such that the edges of a skewed parallelogram would not be considered candidates for bundling).
Additional anti-aliasing was performed on the final output to increase overall smoothing. The resulting graph diagrams are beautiful and very readable.