Parallel Edge Splatting for Scalable Dynamic Graph Visualization

Paper pdf-Version

A Dynamic Graph where the Splatting Technique is Applied

Actually, I got this idea at the IVAPP conference 2011 in Vilamoura, Portugal, at the beautiful Algarve coast after visiting some presentations about graph visualizations. I asked myself how a dynamic graph might be displayed in a static diagram and as little node position changes as possible are used to show trends, countertrends, and anomalies in the time-varying relational data set.

The general idea is to do not map the graph vertices in 2D as an animated sequence of node-link diagrams which would lead to a waste of space on the one hand and cognitive efforts to preserve the mental map caused by animation on the other hand. Furthermore, sophisticated layout algorithms are required to keep the subsequent graph layouts as stable as possible, interactive features are difficult to apply, and an additional hierarchical organization of the vertices is hard to display.

Dynamic Call Graphs of the JUnit Open Source Software Project

I came up with a solution that maps the graph vertices equidistantly to 1D vertical lines and that makes the graph bipartite by copying the original vertex set. Edges are drawn from left to right and the whole sequence is displayed in a side-by-side view with a stable vertex position in each graph diagram. This preserves a viewer's mental map, interactive features can easily be applied, and an additional hierarchical organization of the vertices can also be attached to the diagram. The problem is the increased amount of visual clutter caused by many edge crossings where the mapping from 2D to 1D is to blame.

This drawback is reduced by applying edge splatting which means computing a density field for the link coverage which can be generated in O(|E|) time allowing an interactive exploration of the data. By using edge splatting the link and graph structure is visible again, even for large and dense graphs.

We are still working at the problem of vertex ordering to further reduce visual clutter. Furthermore, the visualization can be made more scalable in the time dimension and it should be evaluated by a controlled user experiment which belongs to future work.

Here are some more beautiful, colorful, and aesthetically pleasing Parallel Edge Splatting diagrams all showing dynamic call graphs extracted from Open Source Software archives. If you like to see your own dynamic graph data as a Parallel Edge Splatting diagram please send me your data.

Dynamic Call Graphs of the CheckStyle Open Source Software Project

Dynamic Call Graphs of the Cobertura Open Source Software Project

Dynamic Call Graphs of the JHotDraw Open Source Software Project