Near-Optimal (1+ε)-Approximate Fully-Dynamic All-Pairs Shortest Paths in Planar Graphs

We study the fully-dynamic all-pair shortest paths (APSP) problem on planar graphs: given an$n-\mathbf{vertex}$planar graph$G=(V, E)$undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a$(1+\epsilon)-\mathbf{approximate}$dynamic algorithm that supports edge updates and distance queries in$n^{o(1)}$time, for any$1/\mathbf{poly}(\log n) < \epsilon < 1$. Our result is a significant improvement over the best previously known bound of$\tilde{O}(\sqrt{n})$on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a$\Omega(\sqrt{n})$conditional lower-bound on update and query time for exact fully dynamic planar APSP [Abboud and Dahlgaard, FOCS ’16]. The main technical contribution behind our result is to dynamize the planar emulator construction due to [Chang, Krauthgamer, Tan, STOC ’22].