pith. sign in

arxiv: 2605.17498 · v1 · pith:USV2L4UBnew · submitted 2026-05-17 · 💻 cs.CG

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

Lev Nachmanson , Xiaoji Chen This is my paper

Pith reviewed 2026-05-19 22:30 UTC · model grok-4.3

classification 💻 cs.CG
keywords graph visualizationsemantic zoomtile pyramidsleeve routingconstrained Delaunay triangulationedge routingweb browser rendering
0
0 comments X

The pith

Tile pyramids for semantic zoom combined with sleeve routing let large graphs be browsed interactively in the browser like online maps.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper presents a visualization technique that constructs a tile pyramid so that at every zoom level the labels of the highest-ranked nodes stay readable, mirroring how major features remain legible on geographic maps. Edges are routed by sleeve routing, which traverses the dual graph of a constrained Delaunay triangulation to pick a sequence of triangles and then applies the funnel algorithm with heuristics to compute a path inside that sleeve. The complete pipeline of layout, routing, and tile construction runs entirely client-side in a WebGL renderer, and the work reports benchmarks on graphs containing up to 32,768 nodes. A reader would care because the method removes any need for a dedicated server while preserving clarity during zoom and pan operations on sizable networks.

Core claim

The paper establishes that a hierarchy of tiles at successive zoom resolutions, populated with rank-selected node labels and with edges drawn via sleeve routing through free space in a constrained Delaunay triangulation, supports smooth interactive navigation of graphs with tens of thousands of elements while keeping the entire computation inside the browser.

What carries the argument

Sleeve routing, which searches the dual graph of a Constrained Delaunay Triangulation to select a corridor of triangles and then computes a shortest path inside that sleeve using the funnel algorithm together with speed-up heuristics.

Load-bearing premise

Sleeve routing must stay efficient and produce usable non-crossing paths for graphs up to 32,000 nodes when executed entirely in the browser.

What would settle it

A direct browser timing test on one of the 32k-node benchmark graphs in which sleeve routing either exceeds a few seconds or generates paths that cross node labels would show the client-side approach does not deliver the claimed usability.

Figures

Figures reproduced from arXiv: 2605.17498 by Lev Nachmanson, Xiaoji Chen.

Figure 1
Figure 1. Figure 1: The entities rendered on each level are shown without scaling as the user zooms in. [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Two adjacent pyramid levels of the Game of Thrones graph rendered by the WebGL [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: An edge clip, drawn as a polyline, from start to end inside a tile. The two red midlines split the tile into four sub-tiles and meet the polyline at the four points a, b, c, d; at d the polyline touches the horizontal midline without crossing it. Cutting the polyline at these points yields five sub-clips [start, a], [a, b], [b, c], [c, d], [d, end], each contained in one sub-tile and meeting that sub-tile’… view at source ↗
Figure 4
Figure 4. Figure 4: Effect of vertex collapse on the LORAS–RENLY edge of the Game of Thrones graph. [PITH_FULL_IMAGE:figures/full_fig_p008_4.png] view at source ↗
read the original abstract

We present a new way to visualize a large graph in the style of online geographic maps. The method builds a tile pyramid for semantic zoom: at every zoom level the labels of the highest-ranked nodes remain readable, just as the names of major geographical features stay readable on those maps. The edges are routed by a method we call sleeve routing, which searches the dual graph of a Constrained Delaunay Triangulation to select a sequence of triangles through the free space, then applies the funnel algorithm to compute a shortest path inside the selected sleeve. We apply several heuristics to speed up the routing. We implemented our approach in the WebGL renderer of MSAGLJS, an open-source TypeScript library for graph visualization in web browsers, with the entire pipeline running client-side, without a dedicated server. Our benchmark suite contains nine graphs with up to 32,768 nodes and 236,978 edges, and measures browser-side parsing, layout, routing, and tile-pyramid construction. The renderer's demo can be seen at https://microsoft.github.io/msagljs/renderer-webgl-sleeve/index.html. MSAGLJS is available on GitHub (https://github.com/microsoft/msagljs) and as NPM packages (@msagl/core, @msagl/drawing, @msagl/parser, @msagl/renderer-svg, @msagl/renderer-webgl -- all on https://www.npmjs.com/).

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The paper claims a new browser-based visualization method for large graphs that emulates online geographic maps via tile pyramids for semantic zoom, keeping highest-ranked node labels readable at every zoom level. Edges are routed by sleeve routing: searching the dual graph of a Constrained Delaunay Triangulation to select a sequence of triangles, then applying the funnel algorithm inside the sleeve, augmented by several heuristics. The full pipeline (parsing, layout, routing, tile-pyramid construction) is implemented client-side in the WebGL renderer of the open-source MSAGLJS library and evaluated on nine benchmark graphs with up to 32,768 nodes and 236,978 edges; a live demo is provided.

Significance. If the performance claims hold, the work enables practical, server-free interactive visualization of graphs with tens of thousands of nodes directly in web browsers, which is a useful engineering contribution for web-based graph tools. Credit is due for the fully open-source implementation (GitHub and NPM packages), the live demo, and the explicit measurement of the entire client-side pipeline.

major comments (1)
  1. [Benchmark description] Benchmark description (abstract and evaluation section): the manuscript states that the suite 'measures browser-side parsing, layout, routing, and tile-pyramid construction' on graphs up to 32,768 nodes, yet reports no quantitative timings, per-component breakdowns, complexity analysis of sleeve routing, or description of the heuristics. Without these data the central claim that the full pipeline remains interactive client-side cannot be verified.
minor comments (2)
  1. [Abstract] The phrase 'several heuristics' is used without even a high-level list; a one-sentence enumeration or pointer to the relevant subsection would improve clarity.
  2. [Implementation and availability] The live demo URL and GitHub links are helpful; ensure they remain stable and that the repository contains the exact benchmark scripts used.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the thoughtful review and for highlighting the need for more detailed benchmark reporting. We address the major comment below.

read point-by-point responses

  1. Referee: [Benchmark description] Benchmark description (abstract and evaluation section): the manuscript states that the suite 'measures browser-side parsing, layout, routing, and tile-pyramid construction' on graphs up to 32,768 nodes, yet reports no quantitative timings, per-component breakdowns, complexity analysis of sleeve routing, or description of the heuristics. Without these data the central claim that the full pipeline remains interactive client-side cannot be verified.

    Authors: We agree that the current manuscript does not include the quantitative timings, per-component breakdowns, complexity analysis, or heuristic descriptions referenced in the abstract and evaluation section. In the revised version we will add tables and figures reporting wall-clock times (in milliseconds) for parsing, layout, routing, and tile-pyramid construction on each of the nine benchmark graphs; we will also include a per-component breakdown, an asymptotic complexity discussion of the sleeve-routing procedure (dual-graph search plus funnel algorithm), and explicit pseudocode or textual descriptions of the speed-up heuristics. These additions will directly support the claim that the full client-side pipeline remains interactive. revision: yes

Circularity Check

0 steps flagged

No significant circularity: algorithmic pipeline is self-contained

full rationale

The paper describes a visualization system that constructs tile pyramids for semantic zoom and routes edges via sleeve routing on the dual of a Constrained Delaunay Triangulation followed by the funnel algorithm plus heuristics. Sleeve routing is explicitly introduced as a named procedure rather than derived from any fitted parameter or self-referential definition. No equations, uniqueness theorems, or predictions appear that reduce by construction to the paper's own inputs or prior self-citations. Benchmarks consist of direct empirical timings on nine concrete graphs; these measurements do not constitute a derived claim that loops back to the method itself. The entire pipeline is presented as a standard application of known computational-geometry primitives implemented client-side, with no load-bearing self-citation chains or ansatzes smuggled via prior work.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 1 invented entities

The approach depends on standard computational geometry results for Constrained Delaunay Triangulation and the funnel algorithm, plus the practical assumption that heuristics suffice for browser performance on the tested graph sizes. No new physical entities or fitted constants are introduced.

axioms (2)
  • domain assumption Constrained Delaunay Triangulation produces a valid partition of free space around graph nodes for routing purposes
    Invoked when describing sleeve construction from the dual graph.
  • standard math The funnel algorithm computes a shortest path inside a selected sleeve of triangles
    Standard result from computational geometry used without re-derivation.
invented entities (1)
  • Sleeve routing no independent evidence
    purpose: To select and route edges through free space using triangle sequences and funnel paths
    New named procedure introduced to combine dual-graph search with funnel algorithm for graph visualization

pith-pipeline@v0.9.0 · 5782 in / 1489 out tokens · 51801 ms · 2026-05-19T22:30:11.852152+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

47 extracted references · 47 canonical work pages

  1. [1]

    Cosmograph.https://cosmograph.app

    work page

  2. [2]

    deck.gl: Large-scale WebGL-powered data visualization.https://deck.gl/

    work page

  3. [3]

    facebookcombined.https://snap.stanford.edu/data/facebook_combined.txt.gz

    work page

  4. [4]

    https://page.mi.fu-berlin.de/mulzer/notes/alggeo/polySP.pdf

    Funnel algorithm. https://page.mi.fu-berlin.de/mulzer/notes/alggeo/polySP.pdf

    work page

  5. [5]

    Graphviz.http://www.graphviz.org/

    work page

  6. [6]

    Regraph.https://cambridge-intelligence.com/regraph/. 11 Graph|V| |E|ZLT LT total (ms) Frame p95 (ms) Elts/frame max gameofthrones 407 2 639 5 0 0 17.4 2 567 composers 3 405 13 832 9 1 51 18.2 497 ca-GrQc 5 242 28 968 9 0 0 18.2 677 ca-HepTh 9 877 51 946 9 0 0 18.2 383 facebook combined 4 039 88 234 9 0 0 18.0 495 ca-HepPh 12 008 236 978 9 9 556 18.4 1 394...

    work page

  7. [7]

    sfdp.https://graphviz.org/docs/layouts/sfdp/

    work page

  8. [8]

    https://www.sigmajs.org/

    Sigma.js: a JavaScript library aimed at visualizing graphs of thousands of nodes and edges. https://www.sigmajs.org/

    work page

  9. [9]

    Skewed.http://mozart.diei.unipg.it/gdcontest/contest2011/composers.xml

    work page

  10. [10]

    https://deck.gl/docs/api-reference/ geo-layers/tile-layer

    TileLayer ( @deck.gl/geo-layers). https://deck.gl/docs/api-reference/ geo-layers/tile-layer. Accessed: 2026

    work page 2026

  11. [11]

    yworks.https://yworks.com/products/yed

    work page

  12. [12]

    ASK-GraphView: A large scale graph visualization system

    James Abello, Frank Van Ham, and Neeraj Krishnan. ASK-GraphView: A large scale graph visualization system. InIEEE Transactions on Visualization and Computer Graphics, volume 12, pages 669–676. IEEE, 2006

    work page 2006

  13. [13]

    The game of game of thrones: Networked concordances and fractal dramaturgy

    Andrew Beveridge and Michael Chemers. The game of game of thrones: Networked concordances and fractal dramaturgy. InReading Contemporary Serial Television Universes, pages 201–225. Routledge, 2018

    work page 2018

  14. [14]

    Mark Keil

    Prosenjit Bose and J. Mark Keil. On the stretch factor of the constrained Delaunay triangulation. In3rd International Symposium on Voronoi Diagrams in Science and Engineering (ISVD), pages 25–31. IEEE, 2006

    work page 2006

  15. [15]

    Eigensolver methods for progressive multidimensional scaling of large data

    Ulrik Brandes and Christian Pich. Eigensolver methods for progressive multidimensional scaling of large data. InGraph Drawing: 14th International Symposium, GD 2006, Karlsruhe, Germany, September 18-20, 2006. Revised Papers 14, pages 42–53. Springer, 2007

    work page 2006

  16. [16]

    A theorem on polygon cutting with applications

    Bernard Chazelle. A theorem on polygon cutting with applications. In23rd Annual Symposium on Foundations of Computer Science (sfcs 1982), pages 339–349. IEEE, 1982

    work page 1982

  17. [17]

    Sur la sphere vide.Izv

    Boris Delaunay et al. Sur la sphere vide.Izv. Akad. Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk, 7(1):793–800, 1934

    work page 1934

  18. [18]

    Efficient triangulation-based pathfinding

    Douglas Demyen and Michael Buro. Efficient triangulation-based pathfinding. InProceedings of the 21st National Conference on Artificial Intelligence (AAAI), pages 942–947, 2006. 12

    work page 2006

  19. [19]

    Imple- menting a general-purpose edge router

    David P Dobkin, Emden R Gansner, Eleftherios Koutsofios, and Stephen C North. Imple- menting a general-purpose edge router. InGraph Drawing: 5th International Symposium, GD’97 Rome, Italy, September 18–20, 1997 Proceedings 5, pages 262–271. Springer, 1997

    work page 1997

  20. [20]

    Sweep-line algorithm for constrained delaunay triangulation

    Vid Domiter and Borut ˇZalik. Sweep-line algorithm for constrained delaunay triangulation. International Journal of Geographical Information Science, 22(4):449–462, 2008

    work page 2008

  21. [21]

    Breaking the sorting barrier for directed single-source shortest paths

    Ran Duan, Jiayi Mao, Xiao Mao, Xinkai Shu, and Longhui Yin. Breaking the sorting barrier for directed single-source shortest paths. InProceedings of the 57th Annual ACM Symposium on Theory of Computing (STOC), 2025.https://arxiv.org/abs/2504.17033

    work page arXiv 2025

  22. [22]

    IPSep-CoLa: An incremental procedure for separation constraint layout of graphs.IEEE Transactions on Visualization and Computer Graphics, 12(5):821–828, 2006

    Tim Dwyer, Yehuda Koren, and Kim Marriott. IPSep-CoLa: An incremental procedure for separation constraint layout of graphs.IEEE Transactions on Visualization and Computer Graphics, 12(5):821–828, 2006

    work page 2006

  23. [23]

    Fast edge-routing for large graphs

    Tim Dwyer and Lev Nachmanson. Fast edge-routing for large graphs. InGraph Drawing: 17th International Symposium, GD 2009, Chicago, IL, USA, September 22-25, 2009. Revised Papers 17, pages 147–158. Springer, 2010

    work page 2009

  24. [24]

    Lopes, Gerardo Huck, Yue Dong, Onur Sumer, and Gary D

    Max Franz, Christian T. Lopes, Gerardo Huck, Yue Dong, Onur Sumer, and Gary D. Bader. Cytoscape.js: a graph theory library for visualisation and analysis.Bioinformatics, 32(2):309–311, 2016

    work page 2016

  25. [25]

    Gansner, Yehuda Koren, and Stephen North

    Emden R. Gansner, Yehuda Koren, and Stephen North. Topological fisheye views for visualizing large graphs.IEEE Transactions on Visualization and Computer Graphics, 11(4):457–468, 2005

    work page 2005

  26. [26]

    Gansner and Stephen C

    Emden R. Gansner and Stephen C. North. An open graph visualization system and its applications to software engineering.Software: Practice and Experience, 30(11):1203–1233, 2000

    work page 2000

  27. [27]

    Leonidas Guibas, John Hershberger, Daniel Leven, Micha Sharir, and Robert E. Tarjan. Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons.Algorithmica, 2(1–4):209–233, 1987

    work page 1987

  28. [28]

    A fast multi-scale method for drawing large graphs

    David Harel and Yehuda Koren. A fast multi-scale method for drawing large graphs. In Journal of Graph Algorithms and Applications, volume 6, pages 179–202, 2002

    work page 2002

  29. [29]

    Hart, Nils J

    Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic deter- mination of minimum cost paths.IEEE Transactions on Systems Science and Cybernetics, 4(2):100–107, 1968

    work page 1968

  30. [30]

    Computing minimum length paths of a given homotopy class.Computational geometry, 4(2):63–97, 1994

    John Hershberger and Jack Snoeyink. Computing minimum length paths of a given homotopy class.Computational geometry, 4(2):63–97, 1994

    work page 1994

  31. [31]

    An optimal algorithm for Euclidean shortest paths in the plane.SIAM Journal on Computing, 28(6):2215–2256, 1999

    John Hershberger and Subhash Suri. An optimal algorithm for Euclidean shortest paths in the plane.SIAM Journal on Computing, 28(6):2215–2256, 1999

    work page 1999

  32. [32]

    Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data.IEEE Transactions on Visualization and Computer Graphics, 12(5):741–748, 2006

    Danny Holten. Hierarchical edge bundles: Visualization of adjacency relations in hierarchical data.IEEE Transactions on Visualization and Computer Graphics, 12(5):741–748, 2006

    work page 2006

  33. [33]

    Van Wijk

    Danny Holten and Jarke J. Van Wijk. Force-directed edge bundling for graph visualization. InComputer Graphics Forum, volume 28, pages 983–990. Wiley Online Library, 2009

    work page 2009

  34. [34]

    Efficient, high-quality force-directed graph drawing.Mathematica Journal, 10(1):37–71, 2005

    Yifan Hu. Efficient, high-quality force-directed graph drawing.Mathematica Journal, 10(1):37–71, 2005. 13

    work page 2005

  35. [35]

    Graph bundling by kernel density estimation

    Christophe Hurter, Ozan Ersoy, and Alexandru Telea. Graph bundling by kernel density estimation. InComputer graphics forum, volume 31, pages 865–874. Wiley Online Library, 2012

    work page 2012

  36. [36]

    Richard M. Karp. Reducibility among combinatorial problems. In Raymond E. Miller, James W. Thatcher, and Jean D. Bohlinger, editors,Complexity of Computer Computations, pages 85–103. Plenum Press, New York, 1972

    work page 1972

  37. [37]

    Computing many-to-many shortest paths using highway hierarchies

    Sebastian Knopp, Peter Sanders, Dominik Schultes, Falk Schieferdecker, and Dorothea Wagner. Computing many-to-many shortest paths using highway hierarchies. InProceedings of the 9th Workshop on Algorithm Engineering and Experiments (ALENEX), pages 36–45. SIAM, 2007

    work page 2007

  38. [38]

    D. T. Lee and Franco P. Preparata. Euclidean shortest paths in the presence of rectilinear barriers.Networks, 14(3):393–410, 1984

    work page 1984

  39. [39]

    Graph evolution: Densification and shrinking diameters.ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2–es, 2007

    Jure Leskovec, Jon Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters.ACM transactions on Knowledge Discovery from Data (TKDD), 1(1):2–es, 2007

    work page 2007

  40. [40]

    Graphmaps: Browsing large graphs as interactive maps

    Lev Nachmanson, Roman Prutkin, Bongshin Lee, Nathalie Henry Riche, Alexander E Holroyd, and Xiaoji Chen. Graphmaps: Browsing large graphs as interactive maps. In Graph Drawing and Network Visualization: 23rd International Symposium, GD 2015, Los Angeles, CA, USA, September 24-26, 2015, Revised Selected Papers 23, pages 3–15. Springer, 2015

    work page 2015

  41. [41]

    Robertson, and Bongshin Lee

    Lev Nachmanson, George G. Robertson, and Bongshin Lee. Drawing graphs with GLEE. In Graph Drawing: 15th International Symposium, GD 2007, pages 389–394. Springer, 2008

    work page 2007

  42. [42]

    The pagerank citation ranking: Bringing order to the web.Stanford InfoLab, 249(373):1–17, 1999

    Lawrence Page, Sergey Brin, Rajeev Motwani, and Terry Winograd. The pagerank citation ranking: Bringing order to the web.Stanford InfoLab, 249(373):1–17, 1999

    work page 1999

  43. [43]

    Cornac: Tackling huge graph visualization with big data infrastructure.IEEE Transactions on Big Data, 6(1):80–92, 2018

    Alexandre Perrot and David Auber. Cornac: Tackling huge graph visualization with big data infrastructure.IEEE Transactions on Big Data, 6(1):80–92, 2018

    work page 2018

  44. [44]

    Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models

    Benedek Rozemberczki and Rik Sarkar. Characteristic Functions on Graphs: Birds of a Feather, from Statistical Descriptors to Parametric Models. InProceedings of the 29th ACM International Conference on Information and Knowledge Management (CIKM ’20), page 1325–1334. ACM, 2020

    work page 2020

  45. [45]

    Delaunay refinement algorithms for triangular mesh generation

    Jonathan Richard Shewchuk. Delaunay refinement algorithms for triangular mesh generation. Computational Geometry, 22(1–3):21–74, 2002

    work page 2002

  46. [46]

    Methods for visual understanding of hierarchical system structures.IEEE Transactions on Systems, Man, and Cybernetics, 11(2):109–125, 1981

    Kozo Sugiyama, Shojiro Tagawa, and Mitsuhiko Toda. Methods for visual understanding of hierarchical system structures.IEEE Transactions on Systems, Man, and Cybernetics, 11(2):109–125, 1981

    work page 1981

  47. [47]

    Michael Wybrow, Kim Marriott, and Peter J. Stuckey. Orthogonal connector routing. Lecture Notes in Computer Science, 5849:219–231, 2010. 14

    work page 2010