---

Accelerating Web-Based Graph Drawing with Bottom-Up GPU Quadtree Construction

WebGPUGraph DrawingPacificVis 2025 VisNoteUICLuminary CloudUtah State

Landon Dyken, Will Usher, Steve Petruzza, Stavros Sintos, and Sidharth Kumar. Accelerating Web-Based Graph Drawing with Bottom-Up GPU Quadtree Construction. 2025 IEEE 18th Pacific Visualization Conference (PacificVis), 2025.

DOI: 10.1109/PacificVis64226.2025.00008

---

使用自底向上 GPU 四叉树构建加速基于 Web 的图绘制

Abstract

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 sub-optimal 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 $\times$ speed-ups for layout creation of relevant graphs while enabling graph drawing for datasets of much larger size.

图绘制（即图布局生成）是可视化中一项计算困难的挑战，需要把图的顶点放置到能够揭示其结构的布局中。 为了可视化大规模图，有效的布局是理解图结构的必要条件。 以往工作已经展示了直接在 Web 浏览器中进行图绘制的潜力，其使用 WebGPU 这一把现代 GPU 完整能力带到 Web 的新 API。 与依赖 CPU 图绘制算法的现有先进 Web 图可视化方法相比，WebGPU 加速方法提升了性能和可扩展性。 然而，我们发现现有 WebGPU 方案在图绘制中使用的四叉树数据结构并非最优。 在本文中，我们实现了一种改进的四叉树数据结构，它采用 Hilbert 空间排序，在 WebGPU 中支持完全可并行化的自底向上构建算法。 我们利用该数据结构并优化四叉树遍历，提出了一种性能大幅提升的图绘制算法。 我们将该方法与现有先进方法进行性能比较，证明其在相关图的布局生成上可实现最高 69.5 $\times$ 的加速，同时支持规模大得多的数据集。

图1：SuiteSparse Matrix Collection 中 Pkustk13 数据集的示例图，包含 94,893 个顶点和 6,616,827 条边。该布局由我们的力导向算法迭代 1000 次生成，在 NVIDIA RTX 4070 Laptop GPU 上仅耗时 5.48 秒。顶点按 Hilbert code 空间顺序着色；我们利用该顺序在 GPU 上高效构建用于力近似的四叉树。

1. Introduction

Efficient visualization of large-scale graphs is critical for numerous fields such as social networks, health science, web search, and road maps. For this task, one of the key problems is graph drawing, which projects a graph, $G=(V,E)$, where $V$ is the set of vertices and $E$ is the set of edges, onto a 2D plane such that each vertex $v\in V$ is assigned a position $P_v$. The goal of graph drawing is to compute these positions in a way that visually captures the structure of the underlying graph. This is a computationally demanding challenge, especially as we see the scale of graph applications continuing to increase steadily.

大规模图的高效可视化对于社交网络、健康科学、Web 搜索和道路地图等众多领域至关重要。 这项任务的关键问题之一是图绘制：它将图 $G=(V,E)$ 投影到二维平面，其中 $V$ 是顶点集合，$E$ 是边集合，并为每个顶点 $v\in V$ 分配位置 $P_v$。 图绘制的目标是以能够直观呈现底层图结构的方式计算这些位置。 这是一项计算需求很高的挑战，尤其是图应用的规模仍在持续增长。

At the same time, as software is increasingly accessed through the web rather than through desktop applications, the browser has emerged as the go-to for deploying visualization tools. This further complicates the challenge of graph drawing, as existing solutions for the web offer poor performance for large-scale graphs due to their reliance on CPU-based algorithms. To address this, GraphWaGu utilized WebGPU to create a framework for GPU-accelerated graph layout creation and rendering in the web that outperforms existing web-based graph libraries.

与此同时，随着软件越来越多地通过 Web 而非桌面应用访问，浏览器已经成为部署可视化工具的首选平台。 这进一步增加了图绘制的难度，因为现有 Web 方案依赖基于 CPU 的算法，在大规模图上性能不佳。 为解决这一问题，GraphWaGu 使用 WebGPU 构建了在 Web 中进行 GPU 加速图布局生成与渲染的框架，其性能优于现有 Web 图形库。

However, while the rest of their graph drawing algorithm is parallelized fully on GPU, GraphWaGu relies on a single-threaded algorithm for quadtree construction, where all vertices of the graph are inserted one after another to build the quadtree in a top-down manner. This greatly constrains the scalability and performance of their system.

然而，尽管 GraphWaGu 图绘制算法的其余部分已在 GPU 上完全并行化，其四叉树构建仍依赖单线程算法：图中的所有顶点依次插入，以自顶向下方式构建四叉树。 这严重限制了该系统的可扩展性与性能。

In our work, we take inspiration from recent work in unstructured volume rendering to propose a modified quadtree data structure that utilizes a Hilbert spatial ordering for a fully parallelizable bottom-up construction algorithm in WebGPU. We uniquely apply this data structure for Barnes-Hut approximation in our force-directed graph drawing algorithm. Additionally, we improve upon GraphWaGu's algorithm by optimizing quadtree traversal for repulsive force computation. Our evaluation shows that our web-based system outperforms GraphWaGu by massive margins on relevant graph sizes while enabling graphs of even larger scale. In summary, our paper makes the following contributions:

在本文中，我们从近期非结构化体渲染工作中获得启发，提出一种改进的四叉树数据结构，它使用 Hilbert 空间排序，在 WebGPU 中实现完全可并行化的自底向上构建算法。 我们首次把该数据结构用于力导向图绘制算法中的 Barnes-Hut 近似。 此外，我们通过优化用于排斥力计算的四叉树遍历，改进了 GraphWaGu 的算法。 评估结果表明，在相关图规模上，我们的 Web 系统大幅优于 GraphWaGu，同时能够处理规模更大的图。 概括而言，本文作出以下贡献：

• Developed a parallel WebGPU-based bottom-up quadtree construction algorithm using Hilbert spatial ordering for use in Barnes-Hut force-directed graph drawing, resulting in huge performance improvement over the state-of-the-art in web-based graph visualization.
• Utilized this quadtree with an optimized traversal approach for graph drawing, resulting in interactive computation for much larger graphs than previously supported (almost 100,000 nodes and 6 million edges).

• 开发了一种基于 WebGPU、采用 Hilbert 空间排序的并行自底向上四叉树构建算法，用于 Barnes-Hut 力导向图绘制，使其性能相较先进 Web 图可视化方法获得巨大提升。
• 将该四叉树与经过优化的遍历方法用于图绘制，从而能够对以往无法支持的大得多的图进行交互式计算（接近 100,000 个节点和 600 万条边）。

2. Background and Related Work

The most widely used methods for creating insightful graph layouts are force-directed algorithms, where forces are modeled between vertices in the input graph, pushing them to positions that fit the graph's structure. These algorithms compute repulsive forces between all pairs of vertices that repel them from each other, along with attractive forces between vertices connected by an edge, pulling them together. These forces are modeled iteratively, and the vertices of the graph are moved every iteration until a suitable layout is attained.

生成具有洞察力的图布局时，使用最广泛的方法是力导向算法；该算法在输入图的顶点之间建模力，把顶点推向符合图结构的位置。 这些算法计算所有顶点对之间使其彼此远离的排斥力，同时计算由边连接的顶点之间把它们拉近的吸引力。 这些力通过迭代方式建模，每次迭代都会移动图的顶点，直到获得合适的布局。

In each iteration, while the cost to compute attractive forces is $O(|E|)$, the cost for directly computing repulsive forces is $O(|V{|}^2)$, making it infeasible for large graphs. There have been many works that address this challenge which reduce the repulsive force computation to $O(|V|\log |V|)$ or $O(|V|)$ through methods such as approximation or random sampling. Among these, the Barnes-Hut (BH) approximation is one of the most widespread techniques. This method constructs a quadtree over the input graph's vertices, augmented with the center of mass and total mass contained in every quadtree node. When computing repulsive forces for a vertex, the quadtree is traversed recursively from the root. If the distance between the vertex and the node's center of mass is above a certain threshold, the node is used to approximate forces for all vertices contained within it; otherwise, all of the node's children are added to the stack for further traversal. This leads to an expected $O(|V|\log |V|)$ running time, as each vertex greatly reduces the number of vertices it needs to compute repulsive forces against.

在每次迭代中，计算吸引力的成本为 $O(|E|)$，而直接计算排斥力的成本为 $O(|V{|}^2)$，因此无法用于大图。 许多工作通过近似或随机采样等方法解决这一挑战，把排斥力计算降至 $O(|V|\log |V|)$ 或 $O(|V|)$。 其中，Barnes-Hut（BH）近似是应用最广泛的技术之一。 该方法在输入图的顶点上构建四叉树，并在每个四叉树节点中附加其包含顶点的质心与总质量。 为某个顶点计算排斥力时，从根节点开始递归遍历四叉树。 如果顶点与节点质心之间的距离超过某一阈值，就用该节点近似其内部所有顶点的力；否则，把该节点的所有子节点加入栈中继续遍历。 这样可获得期望 $O(|V|\log |V|)$ 的运行时间，因为每个顶点需要计算排斥力的对象数量大幅减少。

In this work, we build a system for web-based graph visualization that extends GraphWaGu, which uses a graph drawing algorithm with BH approximation where attractive and repulsive forces are computed on GPU. While GraphWaGu presents the first force-directed graph algorithm in WebGPU, parallel implementations of both force-directed algorithms and quadtree construction have been explored in earlier research. One of the most important works is Warren and Salman, who propose a method for distributed quadtree construction, which was also adapted for force-directed graph drawing by Rahman et al. in a native OpenMP setting. This method begins by assigning a code to each item being inserted into the quadtree by using its spatial Morton order (also known as Z-order). By sorting based on these codes, the items are put in order of spatial proximity, where spatially close items are close in the sorted list.

在本文中，我们构建了一个扩展 GraphWaGu 的 Web 图可视化系统；GraphWaGu 使用采用 BH 近似的图绘制算法，并在 GPU 上计算吸引力和排斥力。 虽然 GraphWaGu 提出了首个 WebGPU 力导向图算法，但更早的研究已经探索过力导向算法和四叉树构建的并行实现。 其中一项重要工作来自 Warren 和 Salman，他们提出了分布式四叉树构建方法；Rahman 等人还在原生 OpenMP 环境中把该方法用于力导向图绘制。 该方法首先使用空间 Morton 顺序（也称 Z-order），为插入四叉树的每个元素分配一个编码。 根据这些编码排序后，元素会按空间邻近性排列，即空间上接近的元素在有序列表中也彼此接近。

After the sort, the items are divided into sets, and each processor creates its own quadtree over its set of items, giving a distributed quadtree. This work was extended by Grama et al. for better load balancing through improved domain decomposition and assignment of subdomains. Grama et al. also replaced the use of Morton codes with Hilbert codes. While these works construct a quadtree in parallel, they are built for using multiple distributed CPU cores, not for GPU acceleration. A popular GPU-accelerated graph drawing algorithm is the ForceAtlas2 implementation by Brinkmann et al., who utilize a CUDA implementation of BH approximation with an irregular tree-based structure and complex traversal.

排序后，元素被划分为多个集合，每个处理器在自己的元素集合上创建四叉树，从而形成分布式四叉树。 Grama 等人扩展了这项工作，通过改进域分解与子域分配获得更好的负载均衡。 Grama 等人还用 Hilbert code 取代了 Morton code。 尽管这些工作并行构建四叉树，但其面向多个分布式 CPU 核，而非 GPU 加速。 一种常用的 GPU 加速图绘制算法是 Brinkmann 等人实现的 ForceAtlas2，它采用基于 CUDA 的 BH 近似实现，并使用不规则树结构和复杂遍历。

Later work by Zhang and Gruenwald, which does not touch on BH approximation or graph drawing, shows how to improve the performance of quadtree construction on GPU by using a bottom-up approach. Here, they sort all items by their Morton code again (using a GPU radix sort), then create the full quadtree directly in one GPU buffer. They do this by successively applying a CUDA reduce by key primitive to build up the tree from the leaves to the root and show that their performance is faster than other parallel implementations. In order to take advantage of GPU acceleration for quadtree construction, we take inspiration from Zhang and Gruenwald and create a bottom-up algorithm.

Zhang 和 Gruenwald 后来的工作虽不涉及 BH 近似或图绘制，但展示了如何通过自底向上方法提升 GPU 上四叉树构建的性能。 他们再次按 Morton code 对所有元素排序（使用 GPU 基数排序），然后直接在一个 GPU buffer 中创建完整四叉树。 他们连续应用 CUDA 的 reduce by key 原语，从叶节点向根节点构建树，并证明该方法快于其他并行实现。 为了利用 GPU 加速四叉树构建，我们从 Zhang 和 Gruenwald 的工作中获得启发，设计了一种自底向上算法。

We differ from their implementation in several key aspects: WebGPU's lack of a reduce by key primitive necessitates us to implement our own method for merging nodes to create the levels of the tree; our quadtree nodes store additional data (center of mass and total mass) for BH approximation; we optimize memory by eliminating empty child nodes; and we parameterize node branching factors rather than fixing them at four. Additionally, insights from unstructured volume rendering guide our choice of Hilbert over Morton ordering to improve spatial locality during tree construction.

我们的实现与其在若干关键方面不同：WebGPU 缺少 reduce by key 原语，因此需要自行实现节点合并方法来生成树的各层；四叉树节点为 BH 近似存储额外数据（质心和总质量）；我们通过消除空子节点来优化内存；并且把节点分支因子参数化，而不是固定为 4。 此外，非结构化体渲染中的经验促使我们选择 Hilbert 排序而非 Morton 排序，以提升构树过程中的空间局部性。

3. Implementation

We propose a web-based algorithm for force-directed graph drawing that can fully utilize the capabilities of modern GPUs. To do this, we begin from the starting point of GraphWaGu, creating an iterative algorithm that models attractive and repulsive forces between vertices to gradually move them towards the lowest energy arrangement. For convergence, a cooling factor is used that slowly reduces the forces being applied every iteration. Because we found their method for attractive force computation to be effective, our algorithm focuses on improving the computation of repulsive forces by overhauling their quadtree construction and traversal methods.

我们提出一种基于 Web 的力导向图绘制算法，能够充分利用现代 GPU 的能力。 为此，我们以 GraphWaGu 为起点，设计一种迭代算法，在顶点之间建模吸引力与排斥力，使顶点逐渐移向能量最低的排列。 为保证收敛，算法使用冷却因子，在每次迭代中缓慢减小所施加的力。 由于我们发现 GraphWaGu 的吸引力计算方法很有效，因此本算法专注于通过重新设计四叉树构建和遍历方法来改进排斥力计算。

The complete pseudocode for our algorithm is given in Algorithm 1. The input to our algorithm consists of the graph $G(V,E)$, the cooling factor (usually set between 0.95 and 0.99), the branching factor $b$ for our modified quadtree, and the approximation factor $\theta$. Each iteration of our algorithm begins by constructing our modified quadtree in parallel, which occurs in Lines 3-17 in the pseudocode and is described in Section 3.1. We then compute attractive forces by using the method of GraphWaGu, shown in Line 18. After this, we use our quadtree to compute repulsive forces in parallel, which occurs in Lines 19-33 in the pseudocode and is described in Section 3.2. Finally, we apply the forces to the vertices of the input graph in parallel and update the cooling factor in Lines 34-38 of the pseudocode.

本算法的完整伪代码见 算法1。 算法输入包括图 $G(V,E)$、冷却因子（通常设为 0.95 到 0.99）、改进四叉树的分支因子 $b$，以及近似因子 $\theta$。 算法的每次迭代首先并行构建改进后的四叉树，对应伪代码第 3-17 行，详见第 3.1 节。 随后，我们使用 GraphWaGu 的方法计算吸引力，如第 18 行所示。 之后，我们使用四叉树并行计算排斥力，对应第 19-33 行，详见第 3.2 节。 最后，我们把力并行施加到输入图的顶点上，并在伪代码第 34-38 行更新冷却因子。

Algorithm 1: Force-directed graph drawing with bottom-up GPU quadtree construction

1. Input: $G(V,E)$, $coolingFactor$, $b$, $\theta$
2. while $coolingFactor\ge \epsilon$ do
3.   for $v\leftarrow 0$ to $|V|$ do in parallel
4.     $H[v]\leftarrow \mathrm{HilbertCode}(V[v])$
5.   end for
6.   $\mathrm{sortByHilbertCodes}(V)$
7.   for $v\leftarrow 0$ to $|V|$ do in parallel
8.     $T[v]\leftarrow \mathrm{TreeNode}(v)$
9.   end for
10.   $s\leftarrow 0$
11.   for $i\leftarrow 0$ to ${\log }_b|V|$ do
12.     $e\leftarrow s+|V|/b^i$
13.     for $j\leftarrow 0$ to $|V|/b^{i+1}$ do in parallel
14.       $T[e+j]\leftarrow$$\mathrm{Merge}(T[s+jb],\dots ,$$T[s+jb+b-1])$
15.     end for
16.     $s\leftarrow e$
17.   end for
18.   $\mathrm{computeAttractiveForces}()$
19.   for $v\leftarrow 0$ to $|V|$ do in parallel
20.     $node\leftarrow root$, $counter\leftarrow 0$, $stack[64]$
21.     while $node\ne null$ do
22.       if $\theta >$$(2.0\cdot node.size)/$$\mathrm{distance}(V[v],node.CoM)$ then
23.         $F[v]\leftarrow$$F[v]+$$node.mass\cdot f_r(V[v],node.CoM)$
24.       else
25.         for $child$ of $node$ do
26.           $stack[counter]\leftarrow child$
27.           $counter\leftarrow counter+1$
28.         end for
29.       end if
30.       $counter\leftarrow counter-1$
31.       $node\leftarrow stack[counter]$
32.     end while
33.   end for
34.   for $i\leftarrow 0$ to $|V|$ do in parallel
35.     $V[i].position\leftarrow$$V[i].position+$$F[i]\cdot coolingFactor$
36.     $F[i]\leftarrow 0$
37.   end for
38.   $coolingFactor\leftarrow$$coolingFactor\cdot$$initialCoolingFactor$
39. end while

3.1 Quadtree Construction

The first step of constructing our modified quadtree is to compute Hilbert codes for each vertex of the input graph in parallel on GPU (Lines 3-5 in Algorithm 1). This is done for each vertex by converting its x and y coordinates to 16 bit unsigned integers, then using bit shift and rotation operations to encode both into one 32 bit unsigned integer code according to the Hilbert spatial ordering. After this, we use a GPU radix sort implemented in WebGPU to sort the vertices of the graph according to these Hilbert codes (Line 6 in Algorithm 1). This step is crucial, as it places vertices together in the buffer based on their spatial proximity.

构建改进四叉树的第一步，是在 GPU 上并行计算输入图每个顶点的 Hilbert code（算法1第 3-5 行）。 对于每个顶点，算法把其 x 和 y 坐标转换为 16 位无符号整数，然后使用位移与旋转操作，按照 Hilbert 空间顺序把二者编码到一个 32 位无符号整数中。 随后，我们使用 WebGPU 实现的 GPU 基数排序，按照这些 Hilbert code 对图的顶点排序（算法1第 6 行）。 这一步至关重要，因为它会根据空间邻近性把顶点放置到 buffer 中的相邻位置。

Next, we create the leaf nodes of the tree in parallel (Lines 7-9 in Algorithm 1), writing out each vertex's minimum containing node with a mass of 1, center of mass (CoM) at the vertex's position, and size of $1/2^{16}$. This size comes from the fact that we are using 16 bits to encode the x and y coordinates of each vertex in a Hilbert code, meaning our minimum spatial subdivision is of size $1/2^{16}$. Because these nodes were built in order from the sorted vertices, they will also be written in the tree with preserved spatial proximity.

接下来，我们并行创建树的叶节点（算法1第 7-9 行），为每个顶点写出包含它的最小节点：质量为 1，质心（CoM）位于顶点位置，大小为 $1/2^{16}$。 该大小源于我们使用 16 位来把每个顶点的 x 和 y 坐标编码为 Hilbert code，因此最小空间划分的大小为 $1/2^{16}$。 由于这些节点按照排序后的顶点顺序构建，它们写入树时也会保持空间邻近性。

Once the leaf nodes of the tree are created, we can apply a bottom-up approach to build the higher levels in parallel through successively merging adjacent nodes. While a quadtree typically subdivides nodes into 4 at every level, we allow this branching factor $b$ to be given as a parameter to our algorithm, although experimentally we found best performance using the typical value of 4. This bottom-up merging process can be seen in Lines 10-17 in Algorithm 1. The merging process iterates ${\log }_b|V|$ times, each iteration $i$ successively creating one of the ${\log }_b|V|$ levels of the tree until the root is reached. Each iteration dispatches $|V|/b^{i+1}$ GPU threads, where each thread merges $b$ adjacent nodes at the current level to create a new node at the level one higher. $s$ and $e$ are used as the starting and ending indices to find the nodes that are being merged at the current iteration.

创建树的叶节点后，我们可以采用自底向上方法，通过连续合并相邻节点，并行构建更高层。 四叉树通常在每一层把节点划分为 4 个子节点，但我们允许把分支因子 $b$ 作为算法参数；实验发现，使用典型值 4 时性能最佳。 这一自底向上的合并过程见 算法1第 10-17 行。 合并过程迭代 ${\log }_b|V|$ 次，每次迭代 $i$ 依次创建树的 ${\log }_b|V|$ 层之一，直至到达根节点。 每次迭代启动 $|V|/b^{i+1}$ 个 GPU 线程，每个线程合并当前层的 $b$ 个相邻节点，在上一层创建一个新节点。 $s$ 和 $e$ 分别作为起止索引，用于定位当前迭代中正在合并的节点。

For our function to merge the $b$ nodes in each thread (defined as "Merge" in the pseudocode), we utilize the fact that each node has a corresponding Hilbert code. We compute the containing node for the $b$ nodes being merged by comparing their Hilbert codes and finding the shared code prefix between all nodes. Because any prefix of a Hilbert code corresponds to a higher level subdivision that contains the original Hilbert code, this prefix effectively gives us the minimum-size containing node for the nodes being merged. The size of this new node is computed with $1/2^{p/2}$, where $p$ is the number of bits in the nodes' shared prefix. The mass of the new node is computed as the sum of the masses of the merged nodes, and the CoM is computed as the average of the merged nodes' CoMs, weighting each by the nodes' mass. We illustrate a simple example of our quadtree construction algorithm in Figure 2.

对于每个线程中合并 $b$ 个节点的函数（伪代码中定义为 Merge），我们利用每个节点都有对应 Hilbert code 这一事实。 我们比较待合并节点的 Hilbert code，并寻找所有节点共有的编码前缀，从而计算包含这 $b$ 个节点的节点。 由于 Hilbert code 的任意前缀都对应一个包含原始 Hilbert code 的更高层空间划分，因此该前缀实际上给出了待合并节点的最小包含节点。 新节点的大小计算为 $1/2^{p/2}$，其中 $p$ 是节点共有前缀的位数。 新节点的质量为被合并节点质量之和，CoM 则是这些节点 CoM 按各节点质量加权后的平均值。 四叉树构建算法的一个简单示例见 图2。

图2：在最小空间划分为 $1/2^2$ 的小型示例上，以分支因子 2 展示四叉树构建算法。A）Hilbert 空间曲线按空间邻近性排列单元格；B）包含 8 个顶点的输入图，顶点按 Hilbert code 着色；C）自底向上构树过程，先按 Hilbert code 排序顶点，再通过查找相邻节点编码的共有前缀逐层生成树。

This algorithm allows us to build our quadtree from the bottom up, recursively merging groups of neighboring vertices to create the spatial partitions of our graph for BH approximation. Because the vertices were initially sorted via a spatial ordering, the partitions created do not become too large and have minimal overlap. This is important for computation of repulsive forces, as inefficient partitioning will slow quadtree traversal and reduce the likelihood of the BH approximation condition being met, resulting in worse performance. We present a visual comparison between spatial partitions produced by unsorted vertices, Morton codes, and Hilbert codes in Figure 3.

该算法使我们能够自底向上构建四叉树：递归合并相邻顶点组，为 BH 近似创建图的空间划分。 由于顶点最初已按空间顺序排序，所生成的划分不会过大，并且重叠很少。 这对排斥力计算很重要，因为低效划分会减慢四叉树遍历、降低满足 BH 近似条件的概率，从而导致更差的性能。 无序顶点、Morton code 与 Hilbert code 生成的空间划分对比见 图3。

图3：采用无序顶点、按 Morton code 排序的顶点或按 Hilbert code 排序的顶点，通过自底向上构建得到的四叉树。顶点按其四叉树包含节点着色。无序顶点产生低效空间划分；Morton 排序受 Z-order 跳跃影响；Hilbert 排序凭借更优的聚类性质，能保持四叉树节点内顶点的空间邻近性。

3.2 Repulsive Force Computation

In GraphWaGu, repulsive force computation utilized a large pre-allocated storage buffer as a pseudo-stack to complete a breadth-first quadtree traversal for each vertex in parallel. While the rest of our algorithm for computing repulsive forces is similar, we remove the need to use a storage buffer for the stack by simply replacing the breadth-first quadtree traversal with a depth-first quadtree traversal. Removing the large stack buffer improves overall performance and enables our algorithm to compute layouts for larger graphs than GraphWaGu, as this buffer was the memory bottleneck for many input graphs.

在 GraphWaGu 中，排斥力计算使用一个大型预分配 storage buffer 作为伪栈，以并行为每个顶点完成广度优先四叉树遍历。 我们的排斥力计算算法其余部分与之相似，但只需把广度优先四叉树遍历替换为深度优先遍历，就能消除作为栈使用的 storage buffer。 移除大型栈 buffer 提升了整体性能，并使算法能够为比 GraphWaGu 更大的图计算布局，因为该 buffer 是许多输入图的内存瓶颈。

Our repulsive force computation is shown in Lines 19-33 of Algorithm 1. This process dispatches a GPU thread for each vertex to compute its own repulsive forces in parallel. Beginning at the root, the thread traverses our quadtree data structure using a stack array of length 64. At each node, there is a check against the BH approximation condition (Line 22 in Algorithm 1), where forces are approximated for all vertices contained in that node if the condition is met. Otherwise, all of the node's children are added to the stack for traversal. Importantly, the traversal pops the last added element off the stack each iteration, rather than the first, resulting in a depth-first traversal and allowing for a much smaller array to maintain the current traversal's stack.

排斥力计算见 算法1第 19-33 行。 该过程为每个顶点启动一个 GPU 线程，并行计算其排斥力。 线程从根节点开始，使用长度为 64 的栈数组遍历四叉树数据结构。 在每个节点处，算法都会检查 BH 近似条件（算法1第 22 行）；如果满足条件，就近似计算该节点包含的所有顶点产生的力。 否则，把节点的所有子节点加入栈中继续遍历。 重要的是，每次迭代从栈中弹出最后加入的元素，而不是第一个元素，因此形成深度优先遍历，并且只需小得多的数组即可维护当前遍历的栈。

4. Evaluation

In this section, we evaluate the performance improvement achieved by our force-directed layout algorithm compared to GraphWaGu. We outline the datasets used for this evaluation in Section 4.1, describe the experimental setup in Section 4.2, and present results in Section 4.3.

在本节中，我们评估力导向布局算法相较 GraphWaGu 获得的性能提升。 第 4.1 节介绍评估所用数据集，第 4.2 节说明实验设置，第 4.3 节给出结果。

4.1 Datasets

To evaluate the performance of our algorithm, we use the same five real undirected graphs from the SuiteSparse Matrix Collection as in GraphWaGu. These datasets, shown in Table 1, were previously used to demonstrate that GraphWaGu's graph drawing outperforms the state-of-the-art CPU-based JavaScript visualization library D3.js. We also include three additional larger datasets from the same collection to show that our algorithm can continue to scale for even larger graphs. Notably, we include the comYoutube dataset, which consists of over 1.1 million nodes, dwarfing the largest dataset used by GraphWaGu by over 30 $\times$ the number of nodes.

为评估算法性能，我们使用与 GraphWaGu 相同的 SuiteSparse Matrix Collection 中五个真实无向图。 这些数据集见 表1；此前它们曾用于证明 GraphWaGu 的图绘制性能优于基于 CPU 的先进 JavaScript 可视化库 D3.js。 我们还加入了同一集合中的三个更大数据集，以证明该算法能够继续扩展到规模更大的图。 其中尤其包括 comYoutube 数据集，它包含超过 110 万个节点，节点数是 GraphWaGu 所用最大数据集的 30 多倍。

表1：用于评估图绘制的图。数据集在规模与密度上各不相同，以展示实现的可扩展性；所有图均为无向二维图。

Graph	Vertices	Edges
sf_ba6000	6,000	5,999
fe_4elt2	11,143	65,636
pkustk02	10,800	399,600
pkustk01	22,044	979,380
finance256	37,376	298,496
finance512	74,752	261,120
pkustk13	94,893	6,616,827
comYoutube	1,134,890	5,975,248

4.2 Experimental Setup

The experimental environment for this project was a laptop system featuring an Intel core i9-13900H processor with 20 cores and a base clock speed of 2.60 GHz, paired with 32 GB of RAM and integrated Intel Iris Xe Graphics. The system also includes a dedicated NVIDIA GeForce RTX 4070 laptop GPU with 8 GB of dedicated VRAM. DirectX 12 was used as the graphics backend with the WebGPU framework. The web application was developed using React JS, and the benchmarks were executed using Node.js v22.12.

本项目的实验环境是一台笔记本电脑，配备 20 核、基础时钟频率 2.60 GHz 的 Intel Core i9-13900H 处理器、32 GB 内存以及集成 Intel Iris Xe Graphics。 该系统还包含一块具有 8 GB 独立显存的 NVIDIA GeForce RTX 4070 Laptop GPU。 WebGPU 框架以 DirectX 12 作为图形后端。 Web 应用使用 React JS 开发，基准测试使用 Node.js v22.12 执行。

For our experiment, we measured the time taken to compute a graph layout for our chosen datasets with both GraphWaGu and our algorithm. In order to showcase the performance of our method on both dedicated and integrated GPUs, we computed our benchmarks on both the integrated Intel Iris Xe Graphics and NVIDIA GeForce RTX 4070 Laptop GPU of the experimental system. To ensure consistency and reliability, we ran both algorithms for 1000 iterations for each dataset and report the average time for one iteration. Because both algorithms have the same BH approximation condition, we used an approximation factor of 2 for all benchmarks to ensure the comparison is fair. All times are reported in milliseconds (ms).

在实验中，我们测量 GraphWaGu 和本算法为所选数据集计算图布局所需的时间。 为了展示本方法在独立 GPU 与集成 GPU 上的性能，我们分别在实验系统的集成 Intel Iris Xe Graphics 和 NVIDIA GeForce RTX 4070 Laptop GPU 上运行基准测试。 为确保一致性与可靠性，我们在每个数据集上运行两种算法各 1000 次迭代，并报告单次迭代的平均时间。 由于两种算法使用相同的 BH 近似条件，我们在所有基准测试中都使用近似因子 2，以确保比较公平。 所有时间均以毫秒（ms）为单位报告。

4.3 Results

Figure 4 and Figure 5 show the average iteration time comparison between GraphWaGu and our algorithm on the dedicated and integrated GPUs respectively. Across all data sizes and both systems, our algorithm consistently outperforms GraphWaGu by a significant margin. The results show that our algorithm achieves speedups ranging from 15.7 $\times$ (sf_ba6000) to 69.5 $\times$ (finance256) on the dedicated GPU, and from 15.0 $\times$ (sf_ba6000) to 35.2 $\times$ (finance256) on the integrated GPU, with the most significant improvements observed for larger datasets. Speedups for the integrated GPU are slightly less than for the dedicated GPU because the performance gain from parallelizing quadtree construction will necessarily be larger with a more powerful GPU.

图4和 图5分别比较了 GraphWaGu 与本算法在独立 GPU 和集成 GPU 上的平均迭代时间。 在所有数据规模和两种系统上，本算法都持续大幅优于 GraphWaGu。 结果表明，本算法在独立 GPU 上获得 15.7 $\times$（sf_ba6000）至 69.5 $\times$（finance256）的加速，在集成 GPU 上获得 15.0 $\times$（sf_ba6000）至 35.2 $\times$（finance256）的加速；规模较大的数据集提升最明显。 集成 GPU 上的加速略低于独立 GPU，因为 GPU 越强大，并行化四叉树构建所带来的性能收益必然越大。

图4：GraphWaGu 与本算法在 RTX 4070 Laptop GPU 上的平均迭代时间（毫秒，对数坐标）。本算法获得 15.7× 至 69.5× 的加速；GraphWaGu 无法为更大的 finance512、pkustk13 和 comYoutube 数据集计算布局。

图5：GraphWaGu 与本算法在集成 Intel Iris Xe Graphics 上的平均迭代时间（毫秒，对数坐标）。本算法获得 15.0× 至 35.2× 的加速；GraphWaGu 无法为更大的 finance512、pkustk13 和 comYoutube 数据集计算布局。

In addition, the lower memory footprint achieved with our depth-first quadtree traversal for repulsive force computation enables layout creation for larger graphs while also improving total iteration performance. This can be seen in our results for the three larger example graphs that lead to memory errors in GraphWaGu (finance512, pkustk13, and comYoutube). We find on both dedicated and integrated GPUs that the iteration times for all graphs except comYoutube remain below the iteration time for even the smallest graph with GraphWaGu. Impressively, we show our method is able to compute one iteration of forces for pkustk13 in only 5.48 ms (182fps) on the dedicated GPU, despite it having almost 100,000 nodes and 6.6 million edges.

此外，用于排斥力计算的深度优先四叉树遍历降低了内存占用，使我们能够为更大的图生成布局，同时提升总体迭代性能。 这一点可从三个较大示例图的结果中看出：finance512、pkustk13 和 comYoutube 都会使 GraphWaGu 发生内存错误。 我们发现，在独立 GPU 和集成 GPU 上，除 comYoutube 外所有图的迭代时间都低于 GraphWaGu 处理最小图时的迭代时间。 尤其值得注意的是，尽管 pkustk13 拥有接近 100,000 个节点和 660 万条边，本方法在独立 GPU 上仅需 5.48 ms（182 fps）即可完成一次力迭代。

In addition, although performance starts to suffer, we show that it is possible to run graph drawing using our algorithm even for a massive graph such as comYoutube (1.1 million nodes) directly in the browser. We note that, although we've restricted these benchmarks to using an approximation factor of 2, a higher approximation factor could be used to greatly improve the iteration time for this massive graph, enabling interactivity at the cost of some accuracy in the resulting layout. We leave analysis of this tradeoff to future work. Overall, these results confirm that our algorithm significantly reduces computation time for layout creation and enables better scalability, demonstrating the effectiveness of leveraging parallelism in WebGPU for scalable and efficient graph visualization.

此外，虽然性能开始下降，但我们证明，即使对于 comYoutube 这样拥有 110 万个节点的超大规模图，也可以直接在浏览器中使用本算法进行图绘制。 需要指出的是，尽管这些基准测试把近似因子限制为 2，但使用更高的近似因子可以大幅缩短该超大图的迭代时间，以牺牲部分布局精度为代价实现交互性。 我们将这一权衡的分析留作未来工作。 总体而言，这些结果确认本算法显著缩短了布局生成的计算时间并提升了可扩展性，证明了利用 WebGPU 并行性实现可扩展、高效图可视化的有效性。

To analyze the specific performance of the steps of our algorithm compared to GraphWaGu, we also include a breakdown for some of the iteration times using the RTX 4070 Laptop GPU in Figure 6. Iteration times are longer than presented in Figure 4 due to the added time from device synchronization to time each algorithm step (around 2-3ms). We compare the iteration times on finance256 for GraphWaGu and our method, along with comYoutube for our method. Results show that our method drastically improves both tree creation and repulsive force computation, although the tree creation improvement is much more significant.

为了分析本算法各步骤相较 GraphWaGu 的具体性能，我们还在 图6中给出了 RTX 4070 Laptop GPU 上部分迭代时间的分解。 由于对每个算法步骤计时需要设备同步并带来额外时间（约 2-3 ms），此处迭代时间比 图4中更长。 我们比较 GraphWaGu 与本方法在 finance256 上的迭代时间，并给出本方法在 comYoutube 上的迭代时间。 结果表明，本方法大幅改善了树构建和排斥力计算，不过树构建的提升更加显著。

When scaling up to larger datasets, while the iteration times for GraphWaGu are dominated by the quadtree construction step, the majority of iteration time in our method comes from the computation of repulsive forces. From this, we see that the performance improvements of our method can be attributed to the parallelization of our tree construction algorithm, which effectively divides the workload among GPU threads, compared to the single-threaded construction algorithm used by GraphWaGu.

当扩展到更大的数据集时，GraphWaGu 的迭代时间主要由四叉树构建步骤占据，而本方法的大部分迭代时间来自排斥力计算。 由此可见，本方法的性能提升可归因于树构建算法的并行化：与 GraphWaGu 使用的单线程构建算法相比，它能够有效地在 GPU 线程之间分配工作负载。

图6：在 RTX 4070 Laptop GPU 上，GraphWaGu 与本算法针对所选数据集的各步骤平均耗时。为每个步骤计时所需的设备同步增加了约 2-3 ms 固定耗时。finance256 结果表明，本方法显著缩短树构建与排斥力计算时间；在规模更大的 comYoutube 图上，树构建仍然非常高效，大部分时间用于排斥力计算。

5. Conclusion

We have presented an approach for accelerating web-based graph drawing through a parallel bottom-up quadtree construction algorithm implemented in WebGPU. Our method significantly improves upon the state-of-the-art by utilizing Hilbert spatial ordering for efficient GPU quadtree construction and optimizing quadtree traversal for force computation. The experimental results demonstrate massive performance gains, with speedups ranging from 15.7 $\times$ to 69.5 $\times$ compared to GraphWaGu on a dedicated GPU, and 15.0 $\times$ to 35.2 $\times$ on integrated graphics.

我们提出了一种通过 WebGPU 实现的并行自底向上四叉树构建算法，加速基于 Web 的图绘制。 本方法利用 Hilbert 空间排序高效地在 GPU 上构建四叉树，并优化用于力计算的四叉树遍历，从而显著改进现有先进方法。 实验结果显示出巨大的性能提升：相较 GraphWaGu，在独立 GPU 上加速 15.7 $\times$ 至 69.5 $\times$，在集成显卡上加速 15.0 $\times$ 至 35.2 $\times$。

Our approach also enables layout creation of much larger graphs than previously possible in web-based environments, successfully handling graphs with almost 100,000 nodes and 6.6 million edges while maintaining interactive performance. Our approach not only improves computational efficiency, but also reduces memory requirements, making our solution particularly well-suited for web-based applications. By leveraging the full capabilities of modern GPUs through WebGPU, we demonstrate that graph visualization can be effectively implemented in web browsers without compromising on performance or scalability.

本方法还使 Web 环境能够为远大于以往规模的图生成布局，在保持交互性能的同时，成功处理接近 100,000 个节点和 660 万条边的图。 本方法不仅提升了计算效率，还降低了内存需求，因此尤其适合基于 Web 的应用。 通过 WebGPU 利用现代 GPU 的完整能力，我们证明图可视化可以在 Web 浏览器中高效实现，而不必牺牲性能或可扩展性。