Breaking Two Barriers for Dynamic Planar Reachability

1 Introduction

• Fully dynamic reachability maintains a directed graph under edge insertions and deletions while answering path-existence queries; sparse graphs lacked known sublinear update and query times together.The general planar online bound was eO(n^2/3), while fixed-embedding or offline settings achieved eO(√n).Source: §1 · p. 2

1.1 The square-root barrier

• The square-root barrier motivates the question: reachability achieves an offline exponent of 0.49, unlike exact undirected planar distances with a conditional n^1/2−o(1) lower bound.The paper says this rules out an analogous lower bound for offline reachability under a static hardness assumption such as the APSP conjecture.Source: §1.2 · p. 3, §1.1 · p. 3

1.2 Our main theorems

• Offline processing takes eO(n + t · n^0.49) deterministic time, while the online structure has O(n^0.664) amortized update and query time with high-probability correctness.The offline bound covers a sequence of t planarity-preserving updates and reachability queries; the online structure is Monte Carlo randomized.Source: §1.2 · pp. 3–4
• The techniques also yield truly sublinear online reachability algorithms for minor-free digraphs.Source: §1.2 · p. 4

1.3 Sparsification in dynamic algorithms

• For 4k + 5 terminals on four faces, every planar reachability emulator needs at least (k − 2)^2 vertices, ruling out the CGH+20 repetitive-compression strategy.The authors note this does not rule out compression methods exploiting properties other than planarity.Source: §1.3 · p. 5
• A new sparsification framework builds near-linear-size reachability emulators for terminals that preserve a weaker-than-planarity property, using VC dimension and the Stabbing Number Theorem.The framework aims to retain a property that allows reachability information to be compressed again.Source: §1.2 · p. 4, §1.3 · p. 6

2.1 A simple offline algorithm

• The simple offline algorithm chunks the event sequence, removes edges among affected vertices, and answers queries using a static emulator plus the current affected subgraph.It computes the emulator at the start of each chunk and searches the union with the current induced graph on affected vertices.Source: §2.1 · p. 6

2.2 Offline reachability with two layers

• Two chunk scales reuse a large-chunk emulator, then compress it to a Y-terminal emulator so queries combine that summary with current Y-edges.The target computation bound is O(|H-hat|·|Y|^(1−δ)+|Y|^C); the selected parameters give M=24/49<1/2.Source: §2.2 · pp. 7–8

2.3 VC-dimension-based emulators

• For bounded-VC reachability sets, a suitable terminal ordering represents each set by few intervals, enabling subquadratic emulator computation and size refinements.The construction computes reachability sets in reverse topological order; partitioning terminals also removes an additive |Y|^O(d) term from the running-time bound.Source: §2.3 · pp. 8–9

2.4 Faithful emulators

• Faithful emulators preserve every vertex's reachability to the terminals, preventing added Steiner vertices from increasing the reachability system's VC dimension.The construction adds edges to marked separator vertices to preserve connections from each emulator vertex to X.Source: §2.4 · pp. 9–10

2.5 Online reachability

• Online maintenance treats inserted-edge endpoints separately from piece boundaries, combining asymmetric emulators to support O(r^0.99)-time maintenance under limited boundary extensions.The resulting emulator collection has size eO(n/pr + r^(1−ε)); choosing r slightly above n^(2/3) yields the desired update time.Source: §2.5 · pp. 11–12

3.1 VC dimension

• VC dimension measures the largest shattered subset; by Sauer–Shelah, a system of dimension d has O(|X|^d) sets.The dual system reverses the roles of the ground set and its sets.Source: §3.1 · p. 13
• Bounded dual VC dimension d yields an ordering with stabbing number O_d(n^(1−1/d) log n), computable in O(n^3(n + m)) time.A set's stabbing number also bounds its representation as a union of intervals in the ordering.Source: §3.1 · p. 13
• Planar reachability systems have VC dimension and dual VC dimension at most three, improving the generic K5-minor-free VC bound of four.Reversing all edges exchanges the dual VC dimension with the reachability system's VC dimension.Source: §3.1 · p. 14

3.2 Reachability emulators

• A reachability emulator preserves reachability from X to Y; faithfulness additionally matches each emulator vertex's X-reachability set to one from the original graph.Faithful emulators can be combined when the graphs overlap only on their specified boundary sets, preserving faithfulness.Source: §3.2 · p. 15
• Covering every pair in X × Y with subsets Xi × Yi lets separate emulators combine into one of size and construction time linear in their total size.The construction uses copies of the separate emulators and links them to the original X and Y vertices.Source: §3.2 · p. 16

4 Constructing a faithful emulator

• Layering and a spanning tree ensure that directed paths stay within two consecutive layers, enabling local processing of separator-path reachability.For each layer, first- and last-reachable vertices on path segments can be computed in linear total time using neighborhoods spanning three layers.Source: §4 · pp. 17, 19
• O(n log k) time yields a faithful emulator with O(k log k) vertices and O(k log^2 k) edges for an n-vertex planar digraph and terminal set X of size k.The theorem constructs the emulator recursively while ensuring it preserves the required reachability for the original terminal set.Source: §4 · pp. 17, 19
• Three ancestor-descendant paths form a balanced separator, letting the construction recurse on components containing at most half the terminals.The paths come from a separator theorem applied to the spanning tree with terminal-indicator weights.Source: §4 · pp. 18–19
• The emulator connects recursively built component emulators to separator-path subpaths and adds edges that preserve routes passing through those paths.Relevant separator vertices are selected from reachability to X, and path connections are encoded using first- and last-reachable vertices.Source: §4 · p. 20
• A novel final construction step preserves reachability from every emulator vertex to X, including vertices outside X, without tracking those vertices as relevant.Avoiding relevant-vertex tracking for Y \ X is identified as crucial to keeping the emulator near-linear in k.Source: §4 · p. 20

• H is a faithful reachability emulator for (G, X).For each v in H, some u in G has ReachH(v, X) = ReachG(u, X).Source: §4 · p. 21
• O(k log k) vertices suffice for H.The vertex set is formed from the recursive-call sets, X, and R, with |R| ≤ 9·|X|.Source: §4 · p. 21
• H has O(k log^2 k) edges.The construction adds edges across recursive calls and from the dipaths and later construction steps.Source: §4 · pp. 21–22
• The algorithm runs in O(n log k) time.At each of the log k recursion levels, it processes vertex-disjoint subgraphs taking O(n) total time.Source: §4 · p. 22

5 Reachability emulators in bounded VC dimension

• With VC dimension and dual VC dimension at most d, the interval representation data structure has stabbing number Od(k^{1−1/d} · log k), retrieval time Od(k^{1−1/d} · log k), and set lookup time Od(k^{1−1/d} · log² k).Element lookup takes O(1) time, while insertion takes Od(k^{d+3}) time.Source: §5 · pp. 22–23
• eO_d(|G| · |X|^{1−1/d}) plus O_d(|X|^{2d+3}) time suffices to compute all reachability sets ReachG(v, X) in an acyclic digraph.The algorithm returns an ordering of X with stabbing number eO_d(|X|^{1−1/d}) and interval representations of the reachability sets.Source: §5 · pp. 24–25
• eO_d(|Y| · |X|^{1−1/d} + |X|) is the size of a reachability emulator for (G, Y, X) when the reachability system and its dual have VC dimension at most d.The construction takes eO_d(|Y| · |X|^{1−1/d} + |X|) time and uses O_d(|X| + |Y|) vertices.Source: §5 · pp. 25–26
• The reachability emulator for (G, Y, X) has size eO_d(|Y| · |X|^{1−δ/d} + |X|); the proof partitions X into q = O(|X|^{1−δ}) blocks, each of size at most ⌈|X|^δ⌉.Source: §5 · p. 27
• Faithful reachability emulators preserve the VC and dual VC dimension bounds, and the same bounds hold when the terminal set is restricted to any subset Z.The corollary applies this preservation to a faithful emulator H for (G, X).Source: §5 · p. 27
• Under VC and dual VC dimensions at most d and a faithful emulator H for (G, X), the algorithm outputs an emulator for (G, Y, Z) of size eO_d(|Y| · |Z|^(1−δ/d) + |Z|).The corollary assumes constants δ ∈ (0,1] and d ≥ 2.Source: §5 · p. 27

6 Offline Dynamic Reachability

• Each chunk of n^25/49 query/update events can be processed in eO(n) total time.The chunk algorithm answers all queries within that total time.Source: §6 · p. 28
• The algorithm identifies event vertices X and builds a faithful emulator for the graph with edges internal to X removed.Because updates affect only pairs in X × X, the graph after removing those edges is unchanged throughout the chunk.Source: §6 · p. 28
• Within each chunk, subchunks use a planar graph R_j and an emulator to obtain a reachability emulator for the affected vertices.The planar graph's reachability set system has VC dimension and dual VC dimension at most three.Source: §6 · p. 28
• For each subchunk, the algorithm builds J_j and answers its queries by depth-first search on J_j ∪ G_i[Y_j].The emulator J_j has size eO(s^5/3), which the analysis bounds by O(s^2) for processing.Source: §6 · p. 28
• Choosing t = n^25/49 and s = n^3/49 balances the stated subchunk costs to yield near-linear chunk processing time.The analysis gives total time eO(n + t^2 · s^-1/3 + t · s^8), with the latter terms summing to 2n for these choices.Source: §6 · pp. 28–29
• eO(n^24/49) average time per event follows from processing large chunks of length n^25/49 in near-linear time.Theorem 1 states the total time as eO(n + t · n^0.49) for a sequence of length t.Source: §6 · pp. 28–29

7.1 Graph partitions

• Kh-minor-free graphs admit O(n log n)-time r-divisions [BKL+26], while planar graphs admit linear-time r-divisions with few holes.Arbitrary endpoint promotions can break the few-holes boundary condition, which the planar construction avoids.Source: §7.1 · pp. 29–30

7.2 The data structure for minor-free graphs

• For fixed h, deterministic fully dynamic reachability on Kh-minor-free digraphs has worst-case update and query time O_h(n^(1−Ω(1/h²))).The structure uses r-divisions and piecewise reachability emulators; its scheduled phase rebuilds are deamortized.Source: §7.2 · pp. 30–32

7.3 Decremental boundary emulator

• For planar digraphs with O(√n) boundary vertices on O(1) disjoint holes, a randomized decremental emulator has size Õ(√n) and total update time Õ(n + k√n), with high-probability correctness.It is initialized in Õ(n) time; k is the number of deletions.Source: §7.3 · p. 32

7.4 The data structure for planar graphs

• During each phase, the planar structure tracks deletions in G− and inserted-edge endpoints B separately, updating piece emulators from subpiece forward/reverse faithful emulators and a decremental boundary emulator.The phase begins with an r-division with few holes and local s-divisions; |B| ≤ 2n/r.Source: §7.4 · p. 33
• Deleting an edge in a piece updates its maintained emulator via Theorem 44, after which the faithful emulators are recomputed.The resulting emulator is correct with high probability.Source: §7.4 · p. 34
• A vertex v is reachable from u in G if and only if it is reachable from u in the query emulator Hu,v.The query temporarily adds {u, v}\(∂R∪B) to B, updates the maintained emulators, and tests reachability in Hu,v.Source: §7.4 · pp. 34–35
• With r = n^37/55, s = n^73/110, and δ = 9/74, the bound is eO(n^73/110) = O(n^0.664).The query cost dominates insertion and deletion costs, excluding updates to the decremental emulator data structure.Source: §7.4 · p. 35

8 Improved VC dimension bound for planar reachability set systems

• Both VC dimension and dual VC dimension of planar reachability set systems are at most three.The proof establishes the VC-dimension bound and uses Lemma 7 to obtain the stated result for both dimensions.Source: §8 · pp. 35–36
• Assuming four vertices are shattered, the proof chooses pair-witness vertices whose reachable targets are exactly each corresponding pair.For each pair, the witness is chosen from the latest strongly connected component in a topological ordering.Source: §8 · p. 36
• The proof constructs pairwise-disjoint connected vertex sets that contract to a subdivision of K4.The construction uses paths from pair-witness vertices to their two targets; the sets V1 through V4 are pairwise disjoint.Source: §8 · pp. 36–37
• The vertex set S must attach in one of six cases, and each resulting minor contains K5 or K3,3, contradicting planarity.The six cases are considered modulo symmetry; the contradiction rules out a shattered four-vertex set.Source: Figure 7 · p. 36, §8 · p. 37

9 Lower bound for planar reachability emulators

• The construction strengthens: its quadratic lower bound for reachability-preserving minors does not rule out smaller planar emulators with rearranged terminals.Figure 8 contrasts the minor lower-bound instance with an O(|T|)-vertex planar emulator when terminal locations may be rearranged.Source: §9 · p. 37, Figure 8 · p. 38
• For every k ≥3, some plane digraph with 4k + 5 terminals on four faces has no planar reachability emulator smaller than (k −2)2 vertices.The lower bound applies to every planar emulator, not only a minor of the original graph.Source: §9 · p. 38
• The proof uses a minimal planar emulator, first ruling out contractible edges and then forcing original edges between terminals to remain present.These constraints support the path and branch-set arguments used to obtain the K5 contradiction.Source: §9 · pp. 38, 40
• Each pair of selected horizontal and vertical paths must intersect, or their disjointness would yield a K5 minor in the emulator.The (k −2)2 distinct intersections imply the vertex lower bound.Source: §9 · pp. 40–41

10 Conclusion

• The paper breaks the O(n1/2) offline and O(n2/3) online barriers for dynamic planar reachability.The authors say the offline result rules out repeating the hardness reduction known for dynamic planar shortest paths [AD16].Source: §10 · p. 41
• The online algorithm’s randomization and amortization come from, and adapting to remove them remains uncertain.A deterministic replacement might yield worst-case bounds below n2/3, but its applicability to Theorem 2 is unclear.Source: §10 · p. 41
• For substantial improvements, avoiding the eO(r) rebalancing bottleneck under boundary-set extensions remains an open direction.Maintaining an r-division with few holes under eO(pr) edge insertions could improve the update bound.Source: §10 · pp. 41–42
• Thorup’s emulators remove the few-holes r-division bottleneck, but approaching n1/2 likely requires dynamizing their construction.Source: §10 · p. 42
• A third chunk layer is obstructed because the second-layer emulator is either quadratic in |Y| or subquadratic but no longer faithful.In the latter case, the authors do not know how to extract smaller emulators in subquadratic time.Source: §10 · p. 42
• Extending the planar results to Kh-minor-free digraphs is challenging because the online method needs few-hole structure and the construction needs separators made of O(1) dipaths.The cited separator construction concerns shortest paths and gives only an unspecified polynomial running time.Source: §10 · pp. 42–43

A Decremental reachability emulator

• The recursive decomposition has O(n) pieces of total size eO(n), with each piece boundary of size O(√n) on O(1) disjoint simple holes.Each non-leaf piece is the union of two children, and its boundary is contained in their boundaries.Source: A Decremental reachability emulator · p. 43
• Reachability on the root boundary is partitioned into submatrices whose row-wise ones have O(1) intervals in a shared ordering.The partition depends on the cyclic order of boundary vertices on the holes, and each row or column participates in O(log |U|) submatrices.Source: A Decremental reachability emulator · pp. 44–45
• As deletions change matrix entries, the structure updates each row’s minimum interval representation in eO(|X|) time for the changed entries.Removing an all-zero column takes eO(1) per row representation; changed row entries are processed together.Source: A Decremental reachability emulator · p. 45
• The interval partition supports an eO(√n)-size reachability emulator for the boundary, constructible in eO(√n) time.The construction builds smaller emulators for submatrix pairs and combines them using a segment-tree representation of intervals.Source: A Decremental reachability emulator · p. 46
• After each deletion, recomputing the boundary emulator takes eO(√n) worst-case time.The stated bound follows by applying the emulator-construction lemma after updating the data structures for the matrix partition.Source: A Decremental reachability emulator · p. 46

B Constructing an r-division with few holes

• [KMS13] gives a linear-time r-division with few face-holes for a simple, triangulated, connected plane graph.The face-hole bounding cycles need not be simple or vertex-disjoint.Source: B Constructing an r-division with few… · p. 46
• The construction embeds, connects, and triangulates the input with auxiliary edges before applying the face-hole decomposition.It then intersects pieces with the original graph and assigns multiply appearing edges to one piece.Source: B Constructing an r-division with few… · p. 46
• Boundary vertices are assigned to chosen holes, and other holes are adjusted to bypass them, producing pairwise disjoint holes.The resulting division satisfies the paper’s definition of an r-division with few holes.Source: B Constructing an r-division with few… · p. 47