Pith. sign in

REVIEW 2 major objections 5 minor 31 references

BFS on planar graphs in sublinear extra space, with full tree queries

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · glm-5.2

2026-07-08 12:49 UTC pith:QWZVRQK7

load-bearing objection BFS on succinct planar encodings with persistent queryable tree — real result, correctness proof has a gap worth scrutinizing the 2 major comments →

arxiv 2607.06221 v1 pith:QWZVRQK7 submitted 2026-07-07 cs.DS cs.ITmath.IT

Breadth-First Search in Succinct Planar Graphs

Johannes Meintrup This is my paper
classification cs.DS cs.ITmath.IT PACS 89.75.Hc
keywords timebitsencodingtreegraphsplanegraphqueries
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

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

This paper proves that a planar graph stored in a succinct encoding (using the information-theoretic minimum number of bits, plus a lower-order overhead) can support a complete breadth-first search from any start vertex in O(n) time using only o(n) additional working bits—meaning the extra space needed beyond the encoding itself is sublinear in the graph size. The resulting BFS tree persists inside the encoding and supports constant-time parent, child, layer, tree-edge, and lowest-common-ancestor queries, plus full traversals. The key obstacle the paper overcomes is that BFS, unlike depth-first search, is not local: a shortest path to an internal vertex of a tiny subgraph may arrive later through a different boundary vertex, so the search cannot simply exhaust each subgraph as it is entered. The solution decomposes the graph into a two-level hierarchy of mini and micro pieces, stores a partial BFS state for each micro piece (a boundary profile encoding visitation status and relative layer ordering of boundary vertices, plus a local advance counter), and uses precomputed lookup-table swaps to advance the BFS inside each micro piece in constant time. Boundary vertices synchronize state across pieces. The paper then applies this structure to compute balanced O(sqrt(n))-size separators of biconnected plane graphs in O(n) time with o(n) bits, to test bipartiteness in o(n) time, and to produce an implicit tree decomposition of width O(d) for graphs of diameter d.

Core claim

The central mechanism is the partial BFS state of a micro piece: a boundary profile (a constant number of colors per micro-boundary vertex encoding visited/unvisited and currently-processing status, plus an ordering capturing relative layer ordering with ties) combined with a local advance (how many layers have been processed inside the micro piece without any boundary change). This pair is small enough to be encoded as part of the lookup-table index for the micro piece, and it is sufficient for a single table-swap operation to compute the next BFS state inside that micro piece—including which internal vertices are reached, their layer offsets, and their parents. The paper claims this state,

What carries the argument

Partial BFS state (boundary profile + local advance) for micro pieces; table-swap operations; nested two-level division into mini and micro pieces; skeleton tree of the interdigitating tree for separator computation

Load-bearing premise

The correctness of the BFS algorithm depends on the claim that the partial BFS state—boundary profile plus local advance—fully determines all local BFS information inside a micro piece, and that a single table-swap query correctly computes the next state. If the boundary profile encoding is insufficient to capture all relevant BFS state (for instance, if two boundary vertices reached in the same round but via different parents lead to different internal vertex assignments), a

What would settle it

Construct a planar graph and a BFS root where two micro-boundary vertices of the same micro piece are reached in the same BFS round via different parents, such that the local parent assignment inside the micro piece depends on which boundary vertex is treated as the reference. If the boundary profile cannot distinguish these cases, the table-swap would produce incorrect parent or layer information for internal vertices. Alternatively, find a case where the arbitrary choice of next state (when multiple valid next states exist) leads to a global inconsistency in the BFS tree—e.g., a cycle in the

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • Succinct planar graph encodings can now serve as drop-in replacements for explicit O(n log n)-bit adjacency structures for any algorithm whose bottleneck is BFS or shortest-path-tree computation, removing the log n space overhead per vertex.
  • The balanced separator computation in sublinear working space means recursive divide-and-conquer on planar graphs (e.g., for shortest paths, max flow, or matching) can be implemented with working space that is o(n) at each recursion level, potentially yielding log-space or near-log-space algorithms for problems currently requiring O(n log n) bits.
  • The implicit tree decomposition of width O(d) available in sublinear space could enable space-efficient parameterized algorithms on planar graphs whose parameter is diameter or treewidth.
  • The technique of encoding algorithmic state (not just graph structure) into lookup-table indices for micro pieces extends beyond BFS: any graph algorithm whose local state on a small subgraph can be summarized by boundary information could be adapted to run on the succinct encoding with sublinear overhead.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 5 minor

Summary. This paper presents a succinct encoding of planar graphs that supports breadth-first search (BFS) directly on the encoding in O(n) time using o(n) additional bits, with the resulting BFS tree supporting standard tree queries (parent, child, layer, LCA, traversal, tree-edge test) in O(1) time per operation. The construction builds on the succinct nested division framework of Blelloch-Farzan and its DFS augmentation by Elberfeld et al., adapting the table-swap mechanism to handle the non-local nature of BFS shortest-path distances. The paper also presents applications: a space-efficient implementation of the planar separator theorem (O(sqrt(n))-size balanced separator in O(n) time and o(n) bits for biconnected plane graphs), bipartiteness testing, and an implicit tree decomposition of width O(d) for triangulated plane graphs of diameter d. The results extend to separable graph classes when no plane embedding is required.

Significance. The paper addresses a natural and important gap in the literature on space-efficient graph algorithms: while DFS on succinct planar encodings was resolved by Elberfeld et al., the BFS case is technically harder because BFS cannot exhaust a micro piece locally (a later entry through another boundary vertex may yield shorter paths). The main result (Theorem 1.7) is a clean, falsifiable algorithmic claim with explicit time and space bounds. The separator application (Theorem 1.13) is a compelling demonstration that the BFS tree structure is usable as a data structure, not just a visitation order. The construction leverages externally verified components (Blelloch-Farzan encoding, Kammer-Meintrup r-division) and provides a self-contained algorithmic contribution on top. The approach is parameter-light: the only free parameters are the piece-size constant alpha, the boundary relaxation epsilon, and the separator balance constant delta, all standard in this setting.

major comments (2)
  1. §3.6–3.7, Claims 3.6–3.9: The correctness of the BFS algorithm (Lemma 3.21) depends on the claim that the partial BFS state—boundary profile plus local advance—fully determines all local BFS information inside a micro piece. The boundary profile stores colors (visited/unvisited/being-processed) and an ordering of boundary vertices encoding 'the relative order of the boundary layers, including ties' (§3.7). However, the paper does not explicitly state whether this ordering encodes the actual layer *differences* between boundary vertices or merely their permutation order. This distinction is load-bearing: if boundary vertex a is at global layer 5 and boundary vertex b at global layer 7, and an internal vertex v is at distance 4 from a (layer 9) and distance 1 from b (layer 8), the correct layer for v is 8. But if the table state only knows 'a before b' without the gap of 2, the table-swap,
  2. query cannot determine that b's wavefront starts at local layer 2 rather than local layer 0, potentially assigning v layer 9 instead of 8. The table-swap operation (§2.21) supports colorings from a universe of size r_1^c for any constant c, which is sufficient to encode layer differences (bounded by r_1). The paper likely uses this capability but does not explicitly state it. The authors should clarify in §3.6–3.7 that the boundary profile encodes the actual layer differences (or offsets) between boundary vertices, not just their relative order, and confirm that this encoding fits within the table-swap color budget. Without this clarification, the correctness of Claims 3.6–3.9 and hence Lemma 3.21 is not fully justified.
minor comments (5)
  1. §3.8: The statement that 'when multiple valid next states exist, one is chosen arbitrarily and fixed in the lookup table' could benefit from a brief argument that this arbitrary choice does not affect correctness of the global BFS tree (only the specific parent assignment, which is still valid). A single sentence would suffice.
  2. §2.12: The use of 'poly(log n)' and 'poly(log log n)' as informal shorthand for 'sufficiently large polylogarithmic functions' is convenient but could be made slightly more precise, e.g., by stating the exponent explicitly in one place for reference.
  3. §3.24: The reference to Elberfeld et al. [11, Sec. 3.2] for the non-BFS-specific tree operations (preorder, postorder, children, parent, tree-edge test, LCA) is appropriate, but a one-sentence summary of why these transfer verbatim would improve self-containedness.
  4. Figure 2: The illustration of boundary synchronization is mentioned but the caption is minimal. Adding labels indicating which direction the synchronization propagates (from which micro piece to which) would aid the reader.
  5. §4.15: The separator construction sketch omits some edge cases (as acknowledged). A brief enumeration of what these edge cases are, or a reference to where the full construction appears, would help the reader assess completeness.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and the constructive recommendation. The referee raises a single major comment concerning the boundary profile in §3.6–3.7: whether it encodes actual layer differences (offsets) between boundary vertices or merely their relative permutation order, and whether this encoding fits within the table-swap color budget. We agree that the manuscript does not state this explicitly enough and will revise accordingly.

read point-by-point responses

  1. Referee: §3.6–3.7, Claims 3.6–3.9: The correctness of the BFS algorithm (Lemma 3.21) depends on the claim that the partial BFS state—boundary profile plus local advance—fully determines all local BFS information inside a micro piece. The boundary profile stores colors (visited/unvisited/being-processed) and an ordering of boundary vertices encoding 'the relative order of the boundary layers, including ties' (§3.7). However, the paper does not explicitly state whether this ordering encodes the actual layer differences between boundary vertices or merely their permutation order. This distinction is load-bearing: if boundary vertex a is at global layer 5 and boundary vertex b at global layer 7, and an internal vertex v is at distance 4 from a (layer 9) and distance 1 from b (layer 8), the correct layer for v is 8. But if the table state only knows 'a before b' without the gap of 2, the table-swap, [

    Authors: The referee is correct that the distinction between encoding actual layer differences versus merely permutation order is load-bearing for correctness, and we agree that the manuscript does not make this sufficiently explicit. We will revise §3.6–3.7 to clarify the following points. (1) The boundary profile encodes the actual layer differences (offsets) between boundary vertices, not merely their relative permutation order. Specifically, for each pair of boundary vertices a and b in a micro piece, the profile stores the integer difference ℓ(a) − ℓ(b), which is bounded in absolute value by r₁ (the micro piece size). This is exactly the information needed to resolve the scenario the referee describes: if a is at global layer 5 and b at global layer 7, the profile stores the offset −2, so when an internal vertex v is at local distance 4 from a and local distance 1 from b, the table can compute layer 5+4=9 versus layer 7+1=8 and correctly assign v to layer 8. (2) This encoding fits within the table-swap color budget. As noted in Definition 2.21, the table-swap operation supports colorings from a universe of size ⌈r₁^c⌉ for any constant c. Since the layer differences are integers in [−r₁, r₁], they can be encoded as colors from a universe of size 2r₁+1, which is well within the budget r₁^c for any c ≥ 1. The number of colors per boundary vertex is a constant (one for visitation status, one for the layer offset relative to a designated reference boundary vertex), so the total number of colorings remains a constant number of colorings of at most r₁^γ distinguished vertices, as required. (3) We will also add an explicit sentence connecting this to the correctness argument in Lemma 3.21, noting that the offset encoding is what allows the table-swap to correctly compute local BFS层 revision: yes

Circularity Check

0 steps flagged

No significant circularity; the BFS-on-succinct-encoding result is a self-contained algorithmic construction built on externally published data structures.

full rationale

The paper's central result (Theorem 1.7) is an algorithmic construction: executing BFS on a succinct planar graph encoding in O(n) time and o(n) bits. The derivation chain rests on three external building blocks: (1) the succinct nested division of Blelloch-Farzan [7], which provides the graph encoding, translation mappings, and basic queries; (2) the table-swap mechanism of Elberfeld et al. [11], which allows precomputing local state transitions in lookup tables; and (3) the space-efficient r-division construction of Kammer-Meintrup [25], which provides the nested division in O(n) time and O(n) bits. The one self-citation, [25] (Kammer and Meintrup), is independently published at ISAAC 2022 with its own correctness proof and is used only for construction-time guarantees (Section 6), not for the correctness of the BFS algorithm itself. The BFS correctness argument (Lemma 3.21, Section 3.5) proceeds by a direct induction over BFS rounds, showing that every edge incident to a layer-d vertex is processed and every vertex at distance d+1 is reached. The partial BFS state mechanism (Section 3.2) is defined constructively: the boundary profile encodes visited/unvisited/being-processed colors and a relative ordering of boundary layers, and the table-swap query precomputes the next state. No step in the derivation chain reduces to its own inputs by definition. The applications (separator theorem, bipartiteness, tree decomposition) follow from the BFS tree plus standard external results (Lipton-Tarjan [28], Klein-Mozes [26]). There is no fitted-parameter-as-prediction pattern, no self-definitional loop, and no uniqueness theorem invoked to force the construction. The paper is self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

3 free parameters · 5 axioms · 0 invented entities

The paper introduces no new mathematical objects, particles, forces, or dimensions. All data structures (nested divisions, skeleton tree, partial BFS states) are compositions of known concepts. The free parameters (alpha, epsilon, delta) are standard in the separable graph literature. The key ad-hoc axiom is the sufficiency of the partial BFS state representation, which is the paper's main technical contribution and is argued but not formally proven.

free parameters (3)
  • alpha (piece size constant) = sufficiently large constant, >= 4
    Controls piece sizes r0 = log^alpha(n) and r1 = (log log n)^alpha. Chosen large enough so that boundary vertices are negligible relative to piece sizes. Not fitted to data but selected to make asymptotic bounds work.
  • epsilon (boundary relaxation) = any fixed value in (0, 1/2)
    Relaxes the boundary vertex bound from O(r^{1/2}) to O(r^{1/2+epsilon}). Used to enable the O(n)-bit r-division construction of [25]. A free parameter in the sense that any value in the range works.
  • delta (separator balance constant) = 3/4
    The balance fraction for the separator. Standard value from the planar separator theorem; not tuned.
axioms (5)
  • domain assumption Succinct nested divisions of planar graphs exist and support basic graph queries, translation mappings, and table-swap operations (Lemma 2.23, citing [7, 11, 25]).
    The entire construction is built on top of this data structure. Its correctness is established in cited external work.
  • domain assumption r-divisions with O(r^{1/2+epsilon}) boundary vertices can be computed in O(n) time and O(n) bits for planar graphs (§2.8, citing [25]).
    Used to achieve the construction-time and space bounds of Corollary 1.9. Self-cited but independently published.
  • standard math The planar separator theorem: every planar graph has a balanced separator of size O(sqrt(n)) (Theorem 1.13, citing [28]).
    The separator application is an implementation of this classical result on the succinct encoding.
  • ad hoc to paper The partial BFS state (boundary profile + local advance) fully determines all local BFS information inside a micro piece (§3.2, Claims 3.6–3.9).
    This is the key structural assumption of the BFS algorithm. It is stated and used but not formally proven as a lemma; correctness is argued informally in §3.5.
  • domain assumption Compressed indexable dictionaries can be constructed in expected linear time (§6, citing [13, 30]).
    Required for the succinct (but not compact) construction. No deterministic linear-time construction is known, which is why the succinct variant is only expected linear time.

pith-pipeline@v1.1.0-glm · 24676 in / 3377 out tokens · 526700 ms · 2026-07-08T12:49:00.741557+00:00 · methodology

0 comments
read the original abstract

We present a succinct encoding of planar graphs that supports executing a breadth-first search directly on the encoding. The succinct encoding can be constructed in expected $O(n)$ time using $O(n)$ bits during construction; a compact variant can be constructed in deterministic $O(n)$ time using $O(n)$ bits. Once the encoding is constructed, a BFS from any start vertex can be computed in $O(n)$ time using $o(n)$ additional bits, including the space needed to represent the BFS tree. The resulting BFS tree $T$ remains available for standard tree operations, such as traversal, parent and child queries, layer queries, and lowest common ancestor queries, in constant time per query or output element. The encoding also supports standard graph queries. For plane graphs $G=(V, E)$, we provide traversal of the interdigitating tree $\hat T$, i.e., the spanning tree of the dual graph whose edges correspond to $E \setminus E(T)$. As our main application, we implement the well-known planar separator theorem in a space-efficient way. For biconnected plane graphs, our encoding allows us to compute a balanced separator of size $O(\sqrt n)$ in $O(n)$ time using $o(n)$ additional bits. Along the way, we show that biconnected plane graphs encoded by our representation can be triangulated in expected $O(n)$ time and $o(n)$ bits in the succinct variant, or in deterministic $O(n)$ time using $O(n)$ bits in the compact variant. Further applications include computation of a tree decomposition of width $O(d)$ where $d$ is the diameter of the plane graph at hand and testing for bipartiteness. Finally, all results that do not rely on a plane embedding generalize to separable graph classes.

Figures

Figures reproduced from arXiv: 2607.06221 by Johannes Meintrup.

Figure 1
Figure 1. Figure 1: The left triangulation of the interior face creates edges that form new boundary vertices. The right [PITH_FULL_IMAGE:figures/full_fig_p008_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration of two boundary synchronizations in a micro piece. The two boundary vertices [PITH_FULL_IMAGE:figures/full_fig_p012_2.png] view at source ↗
Figure 3
Figure 3. Figure 3: On the left, the interdigitating tree Tˆ. Nodes represent faces of the triangulated plane graph, labeled with their weights. Red edges are mini-interface edges. The right side shows the skeleton tree Skel(Tˆ) of Tˆ. 4.9. Since Tˆ is a tree, deleting k mini-interface edges creates k+1 connected components X. By Lemma 2.14, every mini-interface edge crosses a primal edge whose endpoints are mini-boundary ver… view at source ↗

discussion (0)

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

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Succinct data structures for families of interval graphs

    Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, and Srinivasa Rao Satti. Succinct data structures for families of interval graphs. In16th International Symposium on Algorithms and Data Structures (WADS 2019), pages 1––13. Springer, 2019.doi:10.1007/978-3-030-24766-9_1

    work page doi:10.1007/978-3-030-24766-9_1 2019

  2. [2]

    Optimal succinct representations of planar maps

    Luca Castelli Aleardi, Olivier Devillers, and Gilles Schaeffer. Optimal succinct representations of planar maps. In22nd Annual Symposium on Computational Geometry (SCG 2006), pages 309––318. ACM, 2006.doi:10.1145/1137856.1137902

    work page doi:10.1145/1137856.1137902 2006

  3. [3]

    Depth-first search using O(n) bits

    Tetsuo Asano, Taisuke Izumi, Masashi Kiyomi, Matsuo Konagaya, Hirotaka Ono, Yota Otachi, Pascal Schweitzer, Jun Tarui, and Ryuhei Uehara. Depth-first search using O(n) bits. In25th International Symposium on Algorithms and Computation (ISAAC 2014), pages 553–564. Springer, 2014. doi: 10.1007/978-3-319-13075-0_44

    work page doi:10.1007/978-3-319-13075-0_44 2014

  4. [4]

    Brenda S. Baker. Approximation algorithms for NP-complete problems on planar graphs.Journal of the ACM, 41(1):153—-180, January 1994.doi:10.1145/174644.174650

    work page doi:10.1145/174644.174650 1994

  5. [5]

    Space efficient linear time algorithms for BFS, DFS and applications.Theory Comput

    Niranka Banerjee, Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti. Space efficient linear time algorithms for BFS, DFS and applications.Theory Comput. Syst., 62(8):1736–1762, 2018. doi:10.1007/S00224-017-9841-2

    work page doi:10.1007/s00224-017-9841-2 2018

  6. [6]

    Rank-select indices without tears

    Tim Baumann and Torben Hagerup. Rank-select indices without tears. In16th International Symposium on Algorithms and Data Structures (WADS 2019), pages 85–98. Springer, 2019. doi:10.1007/ 978-3-030-24766-9_7

    work page 2019

  7. [7]

    Blelloch and Arash Farzan

    Guy E. Blelloch and Arash Farzan. Succinct representations of separable graphs. In21st Annual Symposium on Combinatorial Pattern Matching (CPM 2010), pages 138–150. Springer, 2010. doi: 10.1007/978-3-642-13509-5_13

    work page doi:10.1007/978-3-642-13509-5_13 2010

  8. [8]

    Biconnectivity, Chain Decom- position and st-Numbering Using O(n) Bits

    Sankardeep Chakraborty, Venkatesh Raman, and Srinivasa Rao Satti. Biconnectivity, Chain Decom- position and st-Numbering Using O(n) Bits. In27th International Symposium on Algorithms and Computation (ISAAC 2016), volume 64 ofLIPIcs, pages 22:1–22:13. Schloss Dagstuhl – Leibniz- Zentrum für Informatik, 2016.doi:10.4230/LIPIcs.ISAAC.2016.22

    work page doi:10.4230/lipics.isaac.2016.22 2016

  9. [9]

    Springer Nature Singapore, Singapore, 2025.doi:10.1007/978-981-96-0668-9_19

    Sankardeep Chakraborty and Kunihiko Sadakane.Succinct Representations of Graphs, pages 295–305. Springer Nature Singapore, Singapore, 2025.doi:10.1007/978-981-96-0668-9_19

    work page doi:10.1007/978-981-96-0668-9_19 2025

  10. [10]

    Orderly spanning trees with applications to graph encoding and graph drawing

    Yi-Ting Chiang, Ching-Chi Lin, and Hsueh-I Lu. Orderly spanning trees with applications to graph encoding and graph drawing. In12th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2001), pages 506–515. SIAM, 2001

    work page 2001

  11. [11]

    Space-efficient depth-first search via augmented succinct graph encodings

    Michael Elberfeld, Frank Kammer, and Johannes Meintrup. Space-efficient depth-first search via augmented succinct graph encodings. In36th International Symposium on Algorithms and Computation (ISAAC 2025), volume 359 ofLIPIcs, pages 29:1–29:16. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2025.doi:10.4230/LIPIcs.ISAAC.2025.29

    work page doi:10.4230/lipics.isaac.2025.29 2025

  12. [12]

    Space-efficient Basic Graph Algorithms

    Amr Elmasry, Torben Hagerup, and Frank Kammer. Space-efficient Basic Graph Algorithms. In32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015), volume 30 of LIPIcs, pages 288–301. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2015. doi:10.4230/ LIPIcs.STACS.2015.288

    work page 2015

  13. [13]

    Linear time succinct indexable dictionary construction with applications

    Guy Feigenblat, Ely Porat, and Ariel Shiftan. Linear time succinct indexable dictionary construction with applications. In26th Data Compression Conference (DCC 2016), pages 13–22, 2016. doi: 10.1109/DCC.2016.70. 19

    work page doi:10.1109/dcc.2016.70 2016

  14. [14]

    Frederickson

    Greg N. Frederickson. Fast algorithms for shortest paths in planar graphs, with applications.SIAM Journal on Computing, 16(6):1004–1022, 1987.doi:10.1137/0216064

    work page doi:10.1137/0216064 1987

  15. [15]

    Geary, Rajeev Raman, and Venkatesh Raman

    Richard F. Geary, Rajeev Raman, and Venkatesh Raman. Succinct ordinal trees with level-ancestor queries.ACM Trans. Algorithms, 2(4):510—-534, 2006.doi:10.1145/1198513.1198516

    work page doi:10.1145/1198513.1198516 2006

  16. [16]

    Goodrich

    M.T. Goodrich. Planar separators and parallel polygon triangulation.Journal of Computer and System Sciences, 51(3):374–389, 1995.doi:10.1006/jcss.1995.1076

    work page doi:10.1006/jcss.1995.1076 1995

  17. [17]

    Space-efficient DFS and applications to connectivity problems: Simpler, leaner, faster

    Torben Hagerup. Space-efficient DFS and applications to connectivity problems: Simpler, leaner, faster. Algorithmica, 82(4):1033–1056, 2020.doi:10.1007/S00453-019-00629-X

    work page doi:10.1007/s00453-019-00629-x 2020

  18. [18]

    Addison-Wesley, 1969

    Frank Harary.Graph Theory. Addison-Wesley, 1969

    work page 1969

  19. [19]

    Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu

    Meng He, J. Ian Munro, Yakov Nekrich, Sebastian Wild, and Kaiyu Wu. Distance Oracles for Interval Graphs via Breadth-First Rank/Select in Succinct Trees. In31st International Symposium on Algorithms and Computation (ISAAC 2020), volume 181, pages 25:1–25:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2020.doi:10.4230/LIPIcs.ISAAC.2020.25

    work page doi:10.4230/lipics.isaac.2020.25 2020

  20. [20]

    Mitchell Hedetniemi, E

    S. Mitchell Hedetniemi, E. J. Cockayne, and S. T. Hedetniemi. Linear algorithms for finding the Jordan center and path center of a tree.Transportation Science, 15(2):98–114, 1981. doi:10.1287/trsc. 15.2.98

    work page doi:10.1287/trsc 1981

  21. [21]

    Algorithm 447: efficient algorithms for graph manipulation.Commun

    John Hopcroft and Robert Tarjan. Algorithm 447: efficient algorithms for graph manipulation.Commun. ACM, 16(6):372—-378, June 1973.doi:10.1145/362248.362272

    work page doi:10.1145/362248.362272 1973

  22. [22]

    Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs

    Taisuke Izumi and Yota Otachi. Sublinear-Space Lexicographic Depth-First Search for Bounded Treewidth Graphs and Planar Graphs. In47th International Colloquium on Automata, Languages, and Programming (ICALP 2020), volume 168 ofLIPIcs, pages 67:1–67:17. Schloss Dagstuhl – Leibniz- Zentrum für Informatik, 2020.doi:10.4230/LIPIcs.ICALP.2020.67

    work page doi:10.4230/lipics.icalp.2020.67 2020

  23. [23]

    PhD thesis, Carnegie Mellon University, 1988

    Guy Joseph Jacobson.Succinct static data structures. PhD thesis, Carnegie Mellon University, 1988

    work page 1988

  24. [24]

    Space-efficient biconnected components and recognition of outerplanar graphs.Algorithmica, 81(3):1180–1204, 2019

    Frank Kammer, Dieter Kratsch, and Moritz Laudahn. Space-efficient biconnected components and recognition of outerplanar graphs.Algorithmica, 81(3):1180–1204, 2019. doi:10.1007/ S00453-018-0464-Z

    work page 2019

  25. [25]

    Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings

    Frank Kammer and Johannes Meintrup. Space-Efficient Graph Coarsening with Applications to Succinct Planar Encodings. In33rd International Symposium on Algorithms and Computation (ISAAC 2022), volume 248 ofLIPIcs, pages 62:1–62:15. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022.doi:10.4230/LIPIcs.ISAAC.2022.62

    work page doi:10.4230/lipics.isaac.2022.62 2022

  26. [26]

    Klein and Shay Mozes

    Philip N. Klein and Shay Mozes. Optimization Algorithms for Planar Graphs. Book draft, accessed 24 June 2026. URL:https://planarity.org/

    work page 2026

  27. [27]

    Klein, Shay Mozes, and Christian Sommer

    Philip N. Klein, Shay Mozes, and Christian Sommer. Structured recursive separator decompositions for planar graphs in linear time. In45th Annual ACM Symposium on Theory of Computing (STOC 2013), pages 505—-514. ACM, 2013.doi:10.1145/2488608.2488672

    work page doi:10.1145/2488608.2488672 2013

  28. [28]

    Lipton and Robert Endre Tarjan

    Richard J. Lipton and Robert Endre Tarjan. A separator theorem for planar graphs.SIAM Journal on Applied Mathematics, 36(2):177–189, 1979.doi:10.1137/0136016

    work page doi:10.1137/0136016 1979

  29. [29]

    Ian Munro, Patrick K

    J. Ian Munro, Patrick K. Nicholson, Louisa Seelbach Benkner, and Sebastian Wild. Hypersuccinct trees - new universal tree source codes for optimal compressed tree data structures and range minima. In29th Annual European Symposium on Algorithms (ESA 2021), volume 204 ofLIPIcs, pages 70:1–70:18. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2021.doi:10...

    work page doi:10.4230/lipics.esa.2021.70 2021

  30. [30]

    Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets.ACM Trans

    Rajeev Raman, Venkatesh Raman, and Srinivasa Rao Satti. Succinct indexable dictionaries with applications to encoding k-ary trees, prefix sums and multisets.ACM Trans. Algorithms, 3(4):43, 2007. doi:10.1145/1290672.1290680

    work page doi:10.1145/1290672.1290680 2007

  31. [31]

    Undirected connectivity in log-space.J

    Omer Reingold. Undirected connectivity in log-space.J. ACM, 55(4), September 2008. doi: 10.1145/1391289.1391291. 21

    work page doi:10.1145/1391289.1391291 2008