Drawing a large network with straight lines produces a "hairball": thousands of crossing edges hide the community structure. Edge bundling fixes this by curving edges so that related ones travel together. One of the more trustworthy variants routes each edge along an actual path of other edges in the graph and draws it as a smooth curve through that path. Because bundles only form where real connections exist, the drawing cannot invent links. The cost is speed. The method recomputes shortest paths for every edge from scratch, so it only works on static graphs. Real networks such as flight schedules, trading streams, and co-authorship growth change continuously, and today nobody can show them with honest bundles as they change.
This proposal makes path-based bundling incremental. When an edge arrives or disappears, the system re-routes only the bundled edges whose routes could have changed, found through an index from each graph edge to the routes that use it. Each curve is stored on the GPU as a short list of node indices rather than as pre-cut line segments, and the graphics card turns those indices into a smooth Bézier curve while drawing. Two things follow from this. Moving a node bends every curve through it without rewriting any edge data. The work per update grows with the size of the change, not with the size of the graph.
Core Claim
Edge-Path Bundling routes each edge $(u,v)$ along the shortest path between $u$ and $v$ through other edges. It accepts that path only if its length is at most $k$ times the straight-line distance, and then renders the path as a Bézier curve (a smooth curve shaped by a few "control points" it bends toward) whose control points are the path's vertices. This motivates the proposal: it shows that topological routing removes false bundles that geometric methods create on noise graphs. It also constrains the proposal: the authors report $O(|E|^2 \log |V|)$ cost and name scalability as the main limitation.
Our claim is that the distortion cap $k$ makes the method local, and that this locality can be used to make it dynamic. A route for $(u,v)$ can only use nodes within distance $k\,\|u-v\|$ of $u$ and $v$. So an inserted edge can only change routes whose endpoints lie inside that radius of it. A deleted edge can only change routes that currently pass through it. If we maintain a reverse index from each graph edge to the routes that use it, along with a spatial grid over edge endpoints, each update affects a bounded set of routes. We re-route each one with a Dijkstra search cut off at the $k$ radius.
The target is exactness. After each batch, the routes should match what static Edge-Path Bundling would produce on the current graph. We also allow a stability-relaxed mode, described in the research program, whose deviation from that output we measure explicitly.
Relation to Prior Work
Two lines of work handle half of this problem each. StreamEB bundles streaming edges using spatial, temporal, neighborhood and data-driven compatibility, with force-directed and quadtree-routed variants. However, its bundles are still driven by geometric attraction or a spatial quadtree. Its curves are segmented approximations rather than compact parametric ones. Its authors name GPU processing as needed future work. We keep StreamEB's goal of preserving the viewer's mental map but replace geometric attraction with topological routing.
GViewer and the WebGL libraries benchmarked in Graph visualization efficiency of popular web-based libraries move layout and drawing onto the GPU. Both draw edges as straight segments of static snapshots, and the second paper's experiments show that browser rendering beyond about 3,000 nodes needs Canvas or WebGL.
The parametric side supplies the representation. DOGE represents road networks as graphs whose edges are cubic Bézier curves and reports 73.2% fewer edges per kilometer than polylines. ABCNet shows that a handful of control points can replace dense boundary descriptions. DOGE's structural changes are heuristic add, merge, prune and split steps applied to static image tiles. Ours are exact responses to a stream of edge events.
The dynamic-maintenance side supplies two techniques:
- The GPU dynamic graph survey, Towards Sufficient GPU-accelerated Dynamic Graph Management, tells us which adjacency structure to use. Sorted and packed-memory arrays such as LPMA favor the neighborhood scans that bounded Dijkstra performs and win on mixed update-and-query workloads. Hash-based structures such as Gunrock update fastest but scan neighbors poorly. All tested systems were memory-bandwidth bound.
- The DiskANN library keeps deleted vertices as temporary routing waypoints and keeps recall above 95% over 50 churn cycles. We borrow this "lazy consolidation" for visual stability.
Research Program
The system has three parts.
Route maintainer. It keeps the current graph in a packed-memory adjacency structure. For each bundled edge it stores its route as a node-index list. It also keeps two indexes:
- the reverse edge-to-routes map;
- a uniform grid over edge endpoints, for the insertion radius test.
Updates arrive in batches, for example one batch per display frame. A batch is processed in three steps. First, collect the routes whose result could change, which is the union of the deletion dependents and the insertion candidates. Then run bounded Dijkstra for each of them in parallel. Finally, rewrite only the index lists that actually changed.
One subtlety needs to be checked. If static Edge-Path Bundling processes edges in an order-dependent way, for example by excluding already-bundled edges from later routing, then one route change can propagate to others. In that case the affected set must be closed under that dependency. We will measure how far these cascades travel, because long cascades would weaken the locality argument.
Lazy consolidation. A route that loses an edge is not redrawn immediately. It keeps a "ghost" copy of the deleted edge as a waypoint for a short grace window, and switches when either the window expires or the replacement route is found. This is DiskANN's consolidation applied to visual stability rather than search recall. It trades exactness for less flicker, and we report both quantities.
Shader renderer. Node positions live in one GPU buffer. Each edge stores an offset into a shared buffer of control-point indices. The vertex shader evaluates the curve at a number of sample points chosen from the edge's on-screen length, so detail is spent only where the curve is visible. When the layout moves nodes, whether from fixed geography or a warm-started force layout in the spirit of the regularized dynamic layout work, only the node buffer changes. Only route changes touch the edge buffers.
Baselines
The naive reference points are straight-line drawing, which shows how much clutter bundling removes, and full static Edge-Path Bundling rerun on every batch. The original paper reports processing US Airlines "in under a second". We will run both static and incremental bundling on the same machine, using the RTX 3060 desktop class from the web library benchmark, with the same $k$ and weighting factor $d$. Beating the full rerun means three things together:
- lower per-batch latency, at a stated matching criterion to static output;
- a larger maximum event rate sustained at 60 frames per second;
- in exact mode, 100% route agreement with static output.
The strongest existing streaming competitor is StreamEB, in both its force-directed and tree-routed variants. No reported runtime was found on Lacuna for StreamEB, so we will reimplement it. Both methods get the same flight streams, the same time window and the same GPU. StreamEB's force iterations get a per-frame time budget equal to our worst-case batch time. Beating StreamEB means:
- equal or lower update latency;
- zero false bundles on noise graphs, where StreamEB's geometric attraction is expected to produce some;
- lower frame-to-frame curve displacement for edges whose routes did not change.
Three ablations each remove one ingredient. The first removes the reverse index and re-routes every edge with an endpoint inside the update radius. The second removes lazy consolidation. The third replaces shader evaluation with curves cut into line segments on the CPU and uploaded as line strips. Each ablation gets the same tuning effort as the full system.
Why not just…?
Why not just rerun static Edge-Path Bundling on a timer? For graphs the size of US Airlines this may be good enough, and we treat it as a real threat. The experiments will find the crossover graph size and event rate at which incremental routing starts to pay off. If that crossover lies beyond the scale of realistic streams, the contribution shrinks to stability. Complete reruns also carry a stability cost. Regularized dynamic layout documents that recomputing from scratch makes nodes "jitter and jump" and destroys the viewer's mental map. Bundles have the same problem: a full rerun can reshuffle bundles even when the graph barely changed, because nothing anchors the new output to the old one. Our stability metric measures this directly.
Why not just put StreamEB on a GPU? That would fix StreamEB's speed but not its honesty. Its bundles still come from spatial attraction, and Edge-Path Bundling shows that geometric bundling hallucinates bundles between unconnected nodes and merges opposing flows. The noise-graph false-bundle count and a direction-separation check on US Flights will settle this.
Why not just cut curves into line segments on the CPU and upload them? This is the simplest rendering path, and at moderate scale bandwidth may not be the bottleneck. In that case the shader design would be an engineering preference rather than a result. The argument for shader evaluation is that the survey found GPU graph pipelines to be memory-bound, and pre-cut segments multiply both buffer size and re-upload volume whenever nodes move. The CPU-segmentation ablation measures bytes uploaded per frame and frame rate as edge count and node motion increase. If the curves do not separate, we will say so. The WebGL slowdown on small graphs reported by Zhao et al. suggests the gap will appear only at scale.
Proposed Experiments
Datasets.
- US Airlines and US Migrations, with fixed geographic positions and edges streamed in random order, to check correctness against the static algorithm.
- The US Flights 1987–2008 stream from StreamEB, as a real high-velocity workload with the September 11 anomaly as a qualitative check.
- AS-733 and the temporal DBLP graph from the dynamic coarsening suite, for evolving abstract graphs laid out with a warm-started layout.
- Synthetic noise graphs, for false bundles.
Metrics.
- per-batch update latency and maximum event rate sustained at 60 frames per second;
- fraction of routes that differ from static output;
- mean control-point displacement for unchanged routes;
- false-bundle count;
- GPU memory per edge and bytes uploaded per frame.
Decisive checks. There are three:
- Exact mode must reproduce static Edge-Path Bundling route for route on every stream.
- The number of routes affected per update should stay roughly constant as the graph grows at fixed density, as the bounded-radius argument predicts. If it grows with $|E|$, the locality claim fails.
- On US Flights, incremental routing should sustain event rates at which the full static rerun drops below interactive frame rates, while keeping zero false bundles on noise graphs.
References
- Edge-Path Bundling: A Less Ambiguous Edge Bundling Approach
- StreamEB: Stream Edge Bundling
- GViewer: GPU-Accelerated Graph Visualization and Mining
- Graph visualization efficiency of popular web-based libraries
- DOGE: Differentiable Bezier Graph Optimization for Road Network Extraction
- ABCNet: Real-Time Scene Text Spotting With Adaptive Bezier-Curve Network
- Towards Sufficient GPU-accelerated Dynamic Graph Management: Survey and Experiment
- The DiskANN library: Graph-Based Indices for Fast, Fresh and Filtered Vector Search
- A regularized graph layout framework for dynamic network visualization
- Adapting to Evolving Graphs: A Scalable Framework for Dynamic Coarsening