Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach

Markus Wallinger, Daniel Archambault, David Auber, Martin Nöllenburg, Jaakko Peltonen

Abstract

Traditional edge bundling techniques reduce visual clutter in network graphs but often introduce "visual lies" by creating false adjacencies between nodes. We present Edge-Path Bundling, a technique that routes edges along existing paths in the graph to ensure topological faithfulness. By using the graph itself as routing infrastructure, this method eliminates ambiguity while maintaining the aesthetic benefits of bundling. Evaluation on synthetic and real-world datasets shows that Edge-Path Bundling significantly reduces false connections and naturally supports directed flows.

Introduction

In network visualization, "edge bundling" is the standard method for decluttering dense "hairball" graphs. Most bundling algorithms, such as Force-Directed or CUBu, group nearby edges into thick "cables" based on geometric proximity. However, these methods suffer from independent edge ambiguity: they often create visual paths between nodes that are not actually connected in the underlying data. This leads to "visual lies," where viewers perceive direct flows that do not exist. While confluent drawings offer a mathematically strict alternative, they are computationally expensive and restrictive. Edge-Path Bundling provides a middle ground, simplifying clutter while remaining topologically honest.

Methods

The core innovation of Edge-Path Bundling is treating the graph's existing edges as the routing infrastructure. Instead of using physics-based forces or image processing, the algorithm routes each edge along a weighted shortest path through the graph's existing vertices.

Edge-Path Bundling routes edges along existing paths of vertices to ensure topological honesty.

The process follows four main steps:

  1. Input: The algorithm starts with an existing graph layout where node positions are already fixed.
  2. Routing: For every edge $(u, v)$, the algorithm identifies the shortest path between $u$ and $v$ using other existing edges in the graph.
  3. Constraints: To avoid excessive detours, a weight factor ($d$) and a distortion threshold ($k$) are applied. If the shortest path exceeds $k$ times the straight-line distance, the edge remains unbundled.
  4. Rendering: The edge is rendered as a smooth Bézier curve, using the vertices along the chosen path as control points.

Because edges are only bundled if a supporting path exists in the data, the resulting visualization is guaranteed to be more faithful to the graph's topology than traditional geometric methods.

Results and Discussion

The authors evaluated Edge-Path Bundling against four state-of-the-art techniques (Straight Line, Force-Directed, CUBu, and Winding Roads) using metrics for ink reduction, distortion, and ambiguity.

Comparison of various edge bundling techniques on the US Airlines dataset. Edge-Path Bundling (e, f) reduces ambiguity compared to geometric methods (b, c, d).

Topological Faithfulness and Ambiguity

Edge-Path Bundling consistently outperformed non-confluent methods in ambiguity tests. In synthetic "noise" tests—where random connections are visualized—traditional methods often "hallucinate" structure by creating flowing bundles. Edge-Path Bundling correctly shows no bundles, as there are no underlying paths to support them.

Directed Flows

A significant advantage of this approach is its natural handling of directionality. By using directed shortest paths, the algorithm can separate "to" and "from" flows (e.g., migration patterns) that other methods typically merge into a single mass. On the US Migrations dataset, this revealed distinct movement streams that were previously obscured.

Performance

The algorithm is efficient for medium-sized graphs, processing the US Airlines dataset in under a second. However, scalability remains a challenge for extremely dense graphs due to the $O(|E|^2 \log |V|)$ complexity of shortest-path calculations.

Conclusion

Edge-Path Bundling offers a robust solution to the ambiguity problem in network visualization. By ensuring that every visual bundle reflects actual connectivity, it provides a more reliable tool for structural analysis. Future work will focus on improving scalability for dense networks and developing layout algorithms specifically optimized for path-based bundling.

Summary updated

BibTeX
@article{wallinger2021edge,
  author = {Markus Wallinger and Daniel Archambault and David Auber and Martin Nöllenburg and Jaakko Peltonen},
  title = {{Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach}},
  journal = {IEEE Trans. Vis. Comput. Graph.},
  year = {2021},
  doi = {10.1109/tvcg.2021.3114795},
}
Figure