{"id":"57a50ead-b1b1-4089-8eb2-e871d69b7e1c","arxiv_id":"2607.06221","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"unknown","formal_verification":"none","parameter_count":3,"one_line_summary":"A succinct encoding of planar graphs supports BFS in O(n) time with o(n) extra bits, keeps the BFS tree queryable, and yields sublinear-space planar separator and bipartiteness algorithms.","lead":"The paper shows how to run breadth-first search directly on a succinct (near-information-theoretic-minimum) encoding of planar graphs in linear time using sublinear extra space, while keeping the BFS tree queryable. This matters because it enables space-efficient planar graph algorithms—like separator computation and bipartiteness testing—to use BFS as a subroutine without materializing the full graph or tree in memory.","discovery_kind":"unclear","skeptic_critique":{"model":"glm-5.2","headline":"Boundary profile encoding (§3.6–3.7) may not explicitly capture inter-boundary layer differences needed for correct local BFS; the mechanism is likely salvageable via the table-swap framework's color budget, but the description is ambiguous.","rationale":"The reader correctly identifies the partial BFS state mechanism (§3.2) as the weakest point in the paper, and the informal correctness argument (§3.20) is a genuine gap. However, the reader's specific concern about arbitrary tie-breaking when two boundary vertices are reached in the same round does not land: same-layer boundary vertices produce equivalent BFS parent choices, and the arbitrary selection does not affect the boundary profile or downstream computations. The more precise concern is whether the boundary profile encoding as described captures inter-boundary layer differences. The paper states the ordering encodes 'the relative order of the boundary layers, including ties' (§3.7), which is ambiguous: a permutation encodes only ordering, not gaps. Without layer differences, the local BFS cannot determine when each boundary vertex's wavefront activates, potentially misassigning internal vertices that are closer to a later-activated boundary vertex. This is a real descriptive gap. However, the table-swap framework (§2.21) explicitly supports colorings from a universe of size r_1^c for any constant c, which can encode layer differences within the space budget. The mechanism is almost certainly salvageable by adding one coloring for relative layer offsets, and the overall approach (nested divisions, boundary synchronization in layer order, table-swap for local advancement) is structurally sound. The key invariant—that boundary vertices are reached in global layer order and synchronized before the local BFS reaches their layer—holds regardless of this encoding detail. The conditional verdict is appropriate: the result is likely correct, but the correctness proof for the state transition mechanism needs to be made rigorous, including an explicit statement of what the boundary profile encodes and a formal proof of the invariant in §3.20.","tokens_in":21782,"tokens_out":22293,"duration_ms":1240345,"concrete_test":"Construct a micro piece with two boundary vertices a, b at layers differing by exactly 2 (e.g., a at layer 5, b at layer 7) and one internal vertex v at distance 4 from a and distance 1 from b, so v's correct BFS layer is 8 (from b). Encode the boundary profile exactly as described in §3.6–3.7 using only the stated colors (visited/unvisited/being-processed) and a permutation ordering of boundary vertices, without an explicit layer-difference field. Run the table-swap query from the initial state (a visited, b unvisited) through local layers 0, 1, 2 (when b should become active). If v is assigned layer 8, the encoding is sufficient. If v is assigned layer 9 or if b's wavefront is incorrectly activated at local layer 0, the boundary profile needs an explicit layer-difference encoding.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The partial BFS state mechanism (§3.2, Claims 3.6–3.9) depends on the boundary profile fully determining the local BFS inside a micro piece. The boundary profile stores (1) colors encoding visited/unvisited/being-processed status and (2) an ordering of boundary vertices encoding 'the relative order of the boundary layers, including ties' (§3.7). The critical question is whether this ordering encodes the actual layer differences between boundary vertices or merely their permutation order. If it is just a permutation, the local BFS cannot determine when each boundary vertex's wavefront becomes active. Concretely: suppose boundary vertex a is at global layer 5, boundary vertex b at global layer 7, and 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 (from b). But if the table state only knows 'a before b' without the gap of 2, the table-swap query cannot determine that b's wavefront starts at local layer 2 rather than local layer 0. This could cause v to be assigned layer 9 (from a) instead of 8. The table-swap operation (§2.21) supports 'a constant number of colorings' with colors from a universe of size r_1^c for any constant c, which is more than sufficient to encode layer differences (bounded by r_1). The paper likely uses this capability but does not explicitly state it. The reader's secondary concern about arbitrary tie-breaking (§3.8) is less load-bearing: when two boundary vertices are at the same layer, any valid parent choice yields a correct BFS tree, and the choice does not propagate into the boundary profile or affect subsequent rounds.","agreement_with_reader":"partial"},"referee_report":{"model":"glm-5.2","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.","tokens_in":22404,"tokens_out":1269,"duration_ms":1404813,"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":[{"comment":"§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,","section":null},{"comment":"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.","section":null}],"minor_comments":[{"comment":"§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.","section":null},{"comment":"§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.","section":null},{"comment":"§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.","section":null},{"comment":"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.","section":null},{"comment":"§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.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The core algorithmic idea is sound and the paper is well-written. The main concern (boundary profile encoding of layer differences) is almost certainly addressable within a revision—it is a clarification/precision issue rather than a fundamental gap. The stress-test concern about arbitrary tie-breaking (§3.8) is less load-bearing: when two boundary vertices are at the same layer, any valid parent assignment yields a correct BFS tree, so the arbitrary choice is fine. The paper fits well within the scope of a algorithms/data structures journal."},"author_rebuttal":{"model":"glm-5.2","summary":"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.","responses":[{"response":"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_made":"yes","referee_comment":"§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, ["}],"tokens_in":21640,"tokens_out":738,"duration_ms":417516,"standing_objections":[]},"desk_editor":{"model":"glm-5.2","letter":"Short version: this paper achieves BFS directly on a succinct planar graph encoding in O(n) time and o(n) extra bits, with the BFS tree persisting for constant-time queries. That fills the gap left by Elberfeld et al.'s DFS result, and the separator application is a natural payoff. The main concern is whether the partial BFS state mechanism (§3.2) is proved rigorously enough; the stress-test flag about boundary profile encoding is the right thing to worry about, though I think it is probably addressable without changing the algorithmic framework.","headline":"BFS on succinct planar encodings with persistent queryable tree — real result, correctness proof has a gap worth scrutinizing","tokens_in":22809,"tokens_out":173,"would_cite":true,"duration_ms":185823,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":["89.75.Hc"],"model":"glm-5.2","headline":"BFS on planar graphs in sublinear extra space, with full tree queries","keywords":[],"falsifier":"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","tokens_in":21963,"feed_emoji":"🌳","tokens_out":1015,"duration_ms":148898,"temperature":0.7,"pith_summary":"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.","feed_headline":"BFS on planar graphs in sublinear extra space, with full tree queries","feed_subtitle":"A succinct encoding lets you run breadth-first search in O(n) time using o(n) working bits and keep the tree for constant-time queries, plus","key_machinery":"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","core_discovery":"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,","pith_inferences":[],"forward_implications":["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."],"fun_headline_variants":["Run BFS on succinct planar graphs using sublinear extra space","Space-efficient BFS for planar graphs with constant-time tree queries","Linear-time BFS on succinct planar graphs using o(n) working bits","Succinct planar graph encoding supports full BFS tree operations","BFS on planar graph encodings in sublinear extra space"],"cache_read_input_tokens":0,"weakest_assumption_plain":"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","fun_headline_variants_meta":{"raw":{"variants":["Run BFS on succinct planar graphs using sublinear extra space","Space-efficient BFS for planar graphs with constant-time tree queries","Linear-time BFS on succinct planar graphs using o(n) working bits","Succinct planar graph encoding supports full BFS tree operations","BFS on planar graph encodings in sublinear extra space","Sublinear-space BFS on planar graphs via succinct encoding"]},"model":"glm-5.2","effort":"high","cost_usd":0.0,"raw_usage":{"total_tokens":1124,"prompt_tokens":667,"completion_tokens":457,"prompt_tokens_details":null},"tokens_in":667,"tokens_out":457,"duration_ms":30549,"temperature":1.0,"reasoning_tokens":377,"cache_read_input_tokens":0,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-08T12:49:00.741557+00:00","model_set":{"reader":"glm-5.2"},"falsifier":"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","supporting_citations":[],"review_version":1}