Dynamic planar graph reachability improved beyond long standing barriers
Breaking Two Barriers for Dynamic Planar Reachability
Data Structures and Algorithms
Summary
The problem of quickly deciding if there is a path between two points in a changing network drawn on a flat surface has been hard to solve efficiently. The authors found new methods to speed up these checks both when all network changes are known ahead of time and when they happen live. They used mathematical ideas about complexity and special graph properties to design faster data structures. This work breaks previous speed limits that had stood for decades.
What this means in practice
- •For network analysts: Speed up reachability queries in evolving planar network models such as road or utility grids with frequent updates.
- •For graph database engineers: Build more efficient infrastructure for dynamic querying in planar graph-based data stores by applying faster reachability data structures.
A theory result. No direct application yet.
Authors
Adam Karczmarz, Michał Włodarczyk
Abstract
We consider the reachability problem in fully dynamic directed planar graphs: the graph undergoes edge updates (insertions and deletions) and we receive queries asking if one vertex is reachable from another. The current-best online algorithm for dynamic planar reachability spends worst-case time $\widetilde{O}(n^{2/3})$ per query/update [Subramanian, ESA '93]. This can be improved to $\widetilde{O}(n^{1/2})$ in the offline setting or when the embedding is fixed [Diks and Sankowski, ESA '07]. Our contribution is twofold: 1. We present the first algorithm that breaks the square-root barrier for dynamic planar reachability in the offline setting, obtaining time ${O}(n^{0.49})$ per query/update. This shows that the problem is easier than answering distance queries in a dynamic undirected planar graph, for which a conditional lower bound of $n^{1/2 - o(1)}$ is known [Abboud and Dahlgaard, FOCS '16]. Notably, this lower bound applies to both online and offline algorithms. 2. Second, in the general online setting we design a randomized data structure with amortized update and query time ${O}(n^{0.664})$. This is the first improvement upon the exponent $2/3$ in over three decades. The main engine behind our theorems is a new sparsification framework aimed at maintaining information about reachability. Specifically, we study digraphs through the lens of VC dimensionality of certain set systems. First, we design sparse reachability emulators for planar digraphs that preserve the VC dimension. Second, we utilize orderings with a low ``stabbing number'' [Chazelle and Welzl, Discrete Comput. Geom. '89] to compute subquadratic reachability emulators in subquadratic time whenever the VC dimension is bounded.