Graph drawing, or graph layout creation, is a computationally difficult challenge in visualization that involves placing the vertices of a graph into a layout that provides insight into its structure. In order to visualize large-scale graphs, effective layouts are necessary for understanding. Previous work has shown the potential for graph drawing directly in the web browser by using WebGPU, a new API that brings the full capabilities of modern GPUs to the web. Compared to the existing state-of-the-art for web-based graph visualization, which rely on CPU-based graph drawing algorithms, WebGPU-accelerated work improves performance and scalability. However, we find that existing WebGPU solutions utilize suboptimal quadtree data structures for graph drawing. In this work, we implement a modified quadtree data structure that uses a Hilbert spatial ordering for a fully parallelizable bottom-up construction algorithm in WebGPU. We utilize this data structure, along with optimizations to the quadtree traversal, to propose a massively more performant graph drawing algorithm. We evaluate the performance of our work against the existing state-of-the-art and demonstrate up to 69.5× speed-ups for layout creation of relevant graphs while enabling graph drawing for datasets of much larger size.

Keywords: Graph layout creation, web-based, quadtree, GPU.

Index Terms: Human-centered computing [Visualization]: Visualization techniques - Graph drawings

PDF

Dyken, L., Usher, W., Petruzza, S., Sintos, S., Kumar, S., Accelerating Web-Based Graph Drawing with Bottom-Up GPU Quadtree Construction, 2025 IEEE 18th Pacific Visualization Conference (PacificVis), Visualization Notes (Visnotes), Taipei, Taiwan, April 22nd, 2025.