Edge Bundling by Rapidly-Exploring Random Trees

We introduce a technique for bundling edges in graphs where a hierarchical organization of the vertices is not available. Instead of applying time-complex force-directed edge bundling, we adopt the concept of Rapidly-Exploring Random Trees (RRTs). We use RRTs for fast computation of a hierarchical space organization that is independent of the spatial structure of the graph layout. Due to this independency, edge bundling can be applied to any graph layout and even allows us to define spatial obstacles through which no bundles may lead. Furthermore, when adding or removing graph nodes and edges on-the-fly, the bundling structure remains stable, which cannot be guaranteed for force-directed bundling. The main benefit of RRT bundling is its high efficiency, supporting interactive exploration. We rely on the low runtime complexity for a new interaction technique for visual clutter reduction in node-link diagrams that we refer to as the RRT edge bundling lens.