Faster Edge‐Path Bundling through Graph Spanners

Edge‐Path bundling is a recent edge bundling approach that does not incur ambiguities caused by bundling disconnected edges together. Although the approach produces less ambiguous bundlings, it suffers from high computational cost. In this paper, we present a new Edge‐Path bundling approach that inc...

Full description

Saved in:
Bibliographic Details
Published in:Computer graphics forum 2023-09, Vol.42 (6), p.n/a
Main Authors: Wallinger, Markus, Archambault, Daniel, Auber, David, Nöllenburg, Martin, Peltonen, Jaakko
Format: Article
Language:English
Subjects:
Algorithms
Bundling
computational geometry
Computing costs
information visualization
visualization
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Edge‐Path bundling is a recent edge bundling approach that does not incur ambiguities caused by bundling disconnected edges together. Although the approach produces less ambiguous bundlings, it suffers from high computational cost. In this paper, we present a new Edge‐Path bundling approach that increases the computational speed of the algorithm without reducing the quality of the bundling. First, we demonstrate that biconnected components can be processed separately in an Edge‐Path bundling of a graph without changing the result. Then, we present a new edge bundling algorithm that is based on observing and exploiting a strong relationship between Edge‐Path bundling and graph spanners. Although the worst case complexity of the approach is the same as of the original Edge‐Path bundling algorithm, we conduct experiments to demonstrate that the new approach is 5–256 times faster than Edge‐Path bundling depending on the dataset, which brings its practical running time more in line with traditional edge bundling algorithms. S‐EPB computes an edge‐path bundling of a straight‐line drawing (a) by bundling along paths in a t‐spanner (b), a sparse sub‐graph, while still avoiding edge ambiguities in the bundled drawing (c).
ISSN:0167-7055
1467-8659
DOI:10.1111/cgf.14789