115 — Force-Directed Edge Bundling for Graph Visualization

One of the main challenges of visualizing spatially embedded graphs with large numbers of high-degree nodes is that of visual clutter: while spatial embedding and distribution of nodes can often reduce the visual complexity of a graph, it also sometimes has the inverse effect; or of course, some graphs are just simply too complex or congested to see every edge.

In this 2009 paper, Holten and van Wijk propose an edge-bundling algorithm that treats each edge like a flexible spring. Each edge can be attracted to other edges, and as a result, these centroids of attraction become “bundles” of multiple edges. Previous edge-bundling algorithms either used a precomputed mesh to drive distortion of edges, or required a manually designed hierarchy. This method requires neither, enabling much higher throughput edge-bundling and graph visualization.

First, each edge is subdivided into a series of points along the “spring” which can be attracted to other points on other edges. Then, a physics simulation is run to allow the springs to come to rest at an energy-optimal resting point.

The bundling strategy can be refined by adding certain restrictions on this attraction: For example, edges that are parallel should bundle more readily than edges that are perpendicular. Short edges should bundle more easily with short edges than long edges (to minimize excess warping).

This algorithm, which was designed in 2009 on a Windows XP machine with 2 GB RAM, now runs easily in the browser using the d3.js renderer, with code available here.