Improving the Performance of Edge-Path Bundling With WebGPU | TU Wien

Information

Publication Type: Bachelor Thesis
Workgroup(s)/Project(s):
- Visualization Group
Date: September 2025
Date (Start): March 2025
Date (End): September 2025
Matrikelnummer: 11776184
First Supervisor:
- Eduard Gröller
- Manuela Waldner

Abstract

Visualizing large graphs is often challenging due to visual clutter, which obscures important patterns. While Spanner-based Edge-Path Bundling (S-EPB) is an effective technique for mitigating this issue, its CPU-based implementation is too slow for interactive use, particularly in web environments. This thesis presents a Parallel Edge-Path Bundling (P-EPB) algorithm that addresses this performance limitation by utilizing the massively parallel processing capabilities of modern Graphics Processing Unit (GPU)s through the WebGPU API.

The proposed algorithm reengineers the S-EPB technique for parallel execution, with a focus on finding and then optimizing the most computationally demanding tasks: spanner construction and shortest-path calculations. A parallelized Floyd–Warshall algorithm, together with different spanner construction methods (greedy and theta-graph), is employed in implementing the P-EPB algorithm as an interactive web application.

A detailed evaluation compares the WebGPU-based P-EPB algorithm to the CPU-based S-EPB implementation. Results show that the P-EPB approach, particularly when using a theta-spanner, delivers substantial speedups on dense graphs. This work highlights the potential of WebGPU to enable high-performance, interactive graph visualization and analysis in web-based environments.

Additional Files and Images

Additional images and videos

teaser

Additional files

thesis

Weblinks

GitHub
demo

BibTeX

@bachelorsthesis{ellhotka-2025-ipo,
  title =      "Improving the Performance of Edge-Path Bundling With WebGPU",
  author =     "Yannic Ellhotka",
  year =       "2025",
  abstract =   "Visualizing large graphs is often challenging due to visual
               clutter, which obscures important patterns. While
               Spanner-based Edge-Path Bundling (S-EPB) is an effective
               technique for mitigating this issue, its CPU-based
               implementation is too slow for interactive use, particularly
               in web environments. This thesis presents a Parallel
               Edge-Path Bundling (P-EPB) algorithm that addresses this
               performance limitation by utilizing the massively parallel
               processing capabilities of modern Graphics Processing Unit
               (GPU)s through the WebGPU API.  The proposed algorithm
               reengineers the S-EPB technique for parallel execution, with
               a focus on finding and then optimizing the most
               computationally demanding tasks: spanner construction and
               shortest-path calculations. A parallelized Floyd–Warshall
               algorithm, together with different spanner construction
               methods (greedy and theta-graph), is employed in
               implementing the P-EPB algorithm as an interactive web
               application.   A detailed evaluation compares the
               WebGPU-based P-EPB algorithm to the CPU-based S-EPB
               implementation. Results show that the P-EPB approach,
               particularly when using a theta-spanner, delivers
               substantial speedups on dense graphs. This work highlights
               the potential of WebGPU to enable high-performance,
               interactive graph visualization and analysis in web-based
               environments.",
  month =      sep,
  address =    "Favoritenstrasse 9-11/E193-02, A-1040 Vienna, Austria",
  school =     "Research Unit of Computer Graphics, Institute of Visual
               Computing and Human-Centered Technology, Faculty of
               Informatics, TU Wien ",
  URL =        "https://www.cg.tuwien.ac.at/research/publications/2025/ellhotka-2025-ipo/",
}