Browsing Large Graphs with Tile Pyramids and Sleeve Routing in the Browser

Source: arXiv:2605.17498 · Published 2026-05-17 · By Lev Nachmanson, Xiaoji Chen

TL;DR

This paper addresses the challenge of interactive large graph visualization directly in web browsers, without requiring dedicated servers. The authors introduce a novel tile pyramid scheme inspired by online geographic maps to enable semantic zooming of large graphs: higher-ranked nodes remain legible at coarser zoom levels, with progressively more detail revealed at finer levels. Additionally, they propose sleeve routing, a new edge routing approach that uses the dual graph of a Constrained Delaunay Triangulation (CDT) combined with the classical funnel algorithm to compute shortest-path polylines that avoid node obstacles. The entire pipeline, implemented in the open-source MSAGLJS TypeScript library, runs client-side with WebGL rendering and achieves smooth pan and zoom with hierarchically tiled vector data. Benchmarks on nine graphs with up to 32,768 nodes and 236,978 edges demonstrate the practical scalability and responsiveness of their approach.

Key findings

• Tile pyramids limit visible elements per tile to ~500 by filtering nodes with PageRank and disallowing label overlaps, enabling semantic zoom across up to 9 levels (Table 1).
• Sleeve routing edges on the CDT dual graph with batched Dijkstra trees speeds routing by 10–63% over per-edge A* search, further improved by ~11–42% vertex cover query reduction heuristic (Table 3).
• Routing quality is near-optimal: total arc length of sleeve router paths are within 2.8% of the full visibility graph optimum on the 407-node Game of Thrones graph (Sec 4.1).
• End-to-end client-side tile pyramid building including layout, routing, and tile generation completes within seconds to a few minutes even on graphs with ~236,000 edges (Table 2).
• Browsing interaction is smooth: 95% of frame render intervals remain below 18.4 ms (~60 Hz), with very few long browser main-thread pauses even on the largest graphs (Table 4).
• Maximum rendered objects per frame stays bounded (e.g. 2500 max edge clips) regardless of total graph size due to tile-level level-of-detail filtering (Table 4).
• Edge routing produces visually stable paths by rerouting at each pyramid level and optionally propagating hints top-down across levels (Sec 4.1).
• Spatial-hash based node overlap testing enables fast label selection and scaling for semantic zoom (Sec 3.1).

Methodology — deep read

1. Threat model & assumptions: The adversary here is not explicitly a security threat but rather the challenge is a user browsing large complex graphs smoothly in a single-threaded web browser environment with limited heap (~4GB). The system assumes a static graph layout without node overlaps.

2. Data: The authors benchmarked on nine diverse graphs including social networks like Game of Thrones (407 nodes, 2639 edges), Snap collaboration networks (up to 23k nodes, 236k edges), a Delaunay mesh, composer collaboration graphs, and an ego Facebook network. These graphs were publicly available or standard benchmarks. Labels and rankings used PageRank computed on the graph.

3. Architecture / algorithm: The pipeline consists of (a) a hierarchy of tiles forming a pyramid from coarse to fine zoom levels; (b) per-level filtering of nodes by PageRank and non-overlapping scaled bounding boxes; (c) edges routed with a novel sleeve routing method that constructs a Constrained Delaunay Triangulation (CDT) over padded node obstacles, uses its dual graph for shortest-path triangle strip search by batched Dijkstra trees per source vertex with vertex cover reduction, and applies the funnel algorithm to compute shortest polylines inside the resulting sleeve polygon. Tiles contain vector geometry of nodes and clipped edge segments, bundled when overlapping.

4. Training regime: Not applicable.

5. Evaluation protocol: Benchmarks measured pipeline stage timings on an Apple M4 Max laptop running headless Chrome 148, including parsing, layout (IPSep-CoLa), routing, and tile pyramid construction with default tile capacity (C=500 elements). Edge routing performance compared per-source Dijkstra trees vs per-edge A* on multiple graphs. Browsing smoothness was evaluated by scripted zoom-in/out dives to random locations measuring frame render intervals and long main thread pauses.

6. Reproducibility: The entire MSAGLJS library and demo are open source on GitHub and NPM packages, enabling reproduction of the pipeline and rendering. The benchmark graphs are public collections.

Concrete example: To build the tile pyramid for a graph, start with a single root tile including all nodes and edges. If number of elements exceeds capacity, split the tile into four sub-tiles and assign nodes and routed edges clipped into these. Continue until each tile has <=500 elements or minimum tile size or memory budget reached, resulting in Z+1 pyramid levels. At each level, nodes are filtered by a PageRank prefix size cut adaptively to contain roughly half of the previous level’s nodes, nodes scaled for non-overlap with spatial hash overlap tests. Edges routed against inflated node obstacles on the CDT dual using batched Dijkstra trees per source with vertex cover to minimize trees, followed by funnel algorithm for shortest path inside the sleeve polygon formed by triangles from the path. Geometry is vector tile clips bundled where possible. The browser uses deck.gl TileLayer to asynchronously fetch and render tiles based on zoom viewport, providing fast pan/zoom with minimal runtime calculations.

Technical innovations

• Semantic zoom tile pyramid construction using PageRank-based adaptive node filtering and non-overlapping scaled bounding boxes for map-like graph navigation in the browser.
• Sleeve routing algorithm that combines shortest-path search on the dual graph of a Constrained Delaunay Triangulation with the funnel algorithm to produce visually stable, shortest geodesic polylines avoiding node obstacles.
• Batching shortest path computations with per-source Dijkstra trees combined with a vertex-cover based heuristic to minimize the number of searches and accelerate routing over the demand graph.
• Integration of vector tile pyramid with WebGL rendering in browsers using deck.gl TileLayer for smooth pan and zoom of graphs with up to hundreds of thousands edges entirely client-side without servers.

Datasets

• gameofthrones — 407 nodes, 2639 edges — publicly available social network
• composers — 3405 nodes, 13832 edges — GD 2011 contest data
• ca-GrQc — 5242 nodes, 28968 edges — SNAP collaboration network
• ca-HepTh — 9877 nodes, 51946 edges — SNAP collaboration network
• ca-HepPh — 12008 nodes, 236978 edges — SNAP collaboration network
• ca-CondMat — 23133 nodes, 186878 edges — SNAP collaboration network
• facebook combined — 4039 nodes, 88234 edges — SNAP ego network
• deezer europe — 28281 nodes, 92752 edges — social network
• delaunay n15 — 32768 nodes, 98274 edges — sparse Delaunay mesh

Baselines vs proposed

• Per-edge A* shortest path search vs Batched per-source Dijkstra trees: sleeve routing speeds up routing by 10–63%, e.g. on facebook combined from 13.31s to 4.88s, on ca-HepPh from 111.2s to 58.07s (Table 3).
• Batched Dijkstra trees vs Vertex-cover reoriented Dijkstra trees: further speedup of 11–42%, e.g. on ca-CondMat from 131.1s to 76.45s (Table 3).
• Route quality of sleeve routing vs full visibility graph shortest paths on Game of Thrones graph: total route length ratio 1.028, max per-edge ratio 1.37 (Sec 4.1).
• Maximum elements rendered per tile limited to ~500 default capacity by tile pyramid, but max tiles can contain 6–8× nodes in worst cases like ca-HepPh (Table 1).
• End-to-end pipeline duration from graph parse to complete tile pyramid between 0.38s (Game of Thrones) up to 172.68s (deezer europe) (Table 2).
• Browsing frame times maintain 95th percentile below 18.4 ms (~60 Hz) across all tested graphs, with few long (>50 ms) pauses even on largest graphs (Table 4).

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2605.17498.

Fig 1: The entities rendered on each level are shown without scaling as the user zooms in.

Fig 2: shows two adjacent pyramid levels built by this procedure; Algorithm 1 summarizes

Fig 3: An edge clip, drawn as a polyline, from start to end inside a tile. The two red

Fig 4 (page 4).

Fig 5 (page 4).

Fig 6 (page 5).

Fig 7 (page 5).

Limitations

• The entire tile pyramid is currently precomputed upfront, incurring seconds to minutes of loading latency for large graphs.
• Some tiles can exceed the target element capacity by large factors (6–8x in densest tiles), leading to uneven rendering load.
• The routing algorithm trades proven shortest-path optimality for speed and does not guarantee globally optimal paths under all conditions.
• Visual stability across zoom levels is improved but not fully guaranteed due to independent routing per level, with the optional routing hint disabled by default due to performance.
• The method assumes static node layouts without node overlaps; dynamic or live-updating graph layouts are not addressed.
• Implementation and benchmarks focus on single-threaded JavaScript V8 engine with 4GB heap limit, not leveraging multi-threading or GPU compute beyond rendering.

Open questions / follow-ons

• How to implement incremental or lazy tile pyramid construction on-demand to reduce time-to-first-frame and scale to larger graphs?
• Can tighter per-tile capacity guarantees be enforced to avoid hotspots with excessive numbers of elements in some tiles?
• How to improve visual stability and route smoothness across zoom levels while maintaining routing speed and scalability?
• Extending sleeve routing and tiling to dynamic or time-varying graphs with frequent node movement or updates.

Why it matters for bot defense

While this work is primarily aimed at scalable visualization of large static graphs in browsers, several ideas may inspire bot-defense and CAPTCHA researchers working on graphical puzzles or interactive image challenges. The tile pyramid semantic zooming approach can be adapted to multi-resolution rendering and element filtering of complex challenge graphs to control visual complexity. The efficient sleeve routing technique could help generate or verify obstacle-aware routes in visual CAPTCHAs that require obstacle avoidance or shortest path demonstrations. The client-side WebGL rendering with precomputed tiled vector geometry is relevant to building smooth, interactive graphical puzzles that run entirely in browsers without server support, maintaining responsiveness despite large puzzle complexity. Finally, the vertex cover heuristic for minimizing shortest-path computations could accelerate verification or synthesis algorithms involving many paths or queries on graph-like challenge structures. However, direct application would require adaptation for adversarial settings with malicious bots, possibly integrating adversarial robustness and anti-automation detection.

Cite

@article{arxiv2605_17498,
  title={ Browsing Large Graphs with Tile Pyramids and Sleeve Routing in the Browser },
  author={ Lev Nachmanson and Xiaoji Chen },
  journal={arXiv preprint arXiv:2605.17498},
  year={ 2026 },
  url={https://arxiv.org/abs/2605.17498}
}

Read the full paper

• arXiv:2605.17498 (abstract)
• arXiv:2605.17498 (PDF)