Near-Optimal $\left(1+\epsilon\right)-\text{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 <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n-\mathbf{vertex}$</tex> planar graph <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$G=(V, E)$</tex> undergoing edge insertions and deletions, the goal is to efficiently process these updates and support distance and shortest path queries. We give a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$(1+\epsilon)-\mathbf{approximate}$</tex> dynamic algorithm that supports edge updates and distance queries in <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$n^{o(1)}$</tex> time, for any <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$1/\mathbf{poly}(\log n) &lt; \epsilon &lt; 1$</tex>. Our result is a significant improvement over the best previously known bound of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\tilde{O}(\sqrt{n})$</tex> on update and query time due to [Abraham, Chechik, and Gavoille, STOC ’12], and bypasses a <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\Omega(\sqrt{n})$</tex> 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].