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

 

Description : Description : images

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.

Description : Description : graphDescription : Description : obstacle

 

Description : Description : shades

Description : Description : extrem

Net-50 graph (464440 edges). Dataset provided by MINGLE

US migration dataset (United States Census Bureau)

Description : USMigrationSmall.Png

 

Description :USMigrationSmallUnbundled.Png

 

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 Groningnen, the Neverland.

 



  • Contact at ENAC: christophe dot hurter at enac.fr