Kernel Density Estimation-based Edge Bundling
Christophe Hurter, Alexandru Telea, and Ozan Ersoy. pdf video slides
Graph Bundling by Kernel Density Estimation.
EuroVis 2012. Computer Graphics Forum
journal.
*new* Visual
Studio C# code instance (GPU version)
Visual Studio C# code instance (CPU
version), thanks to Antoine LHUILLIER
|
Edge bundling is a
recent, increasingly promising, technique which generates graph layouts of
limited clutter. Bundled layouts can be used to get insight into the
coarse-scale structure of networks, geographical maps, and software
systems.
For general graphs,
many bundling methods have been proposed in the last few years. However, the following requirements are still challenging
- bundle graphs of tens..hundreds of
thousands of edges efficiently (near-real-time)
- declutter graphs with many overlapping edges and nodes
- intuitively control the look and feel of the bundling
(e.g. produce smooth or ramified bundles)
- easy implementation (no complex parameter settings or
algorithms)
|
Kernel density estimation
We present here a method
that complies well with the above requirements. The principle of our method
is simple. Given an initial graph drawing
- convert
the drawing to a density map using kernel density estimation (KDE)
- compute
the normalized density map gradient
- move
each edge in the gradient direction
- smooth
edges using Laplacian filtering (optionally)
- repeat
from step 1 with decreasing kernel sizes
Intuitively, the above is
equivalent to sharpening the edges' density map. This in turn pulls
edges towards the center of their local point spatial distribution, which
achieves the bundling.
US
migration dataset (United States Census Bureau)
Implementation
KDEEB is simple to
implement and can be easily accelerated using texture splatting for the computation
of density maps and their gradients. Our entire implementation is done in C#
using OpenGL 1.1.
Acknowledgements
This research was done in
collaboration with Ozan Ersoy
and Alexandru Telea from university of Groningen, the Netherlands.
|