Fully Dynamic All-Pairs Min Cuts on Planar Graphs via Planar Pattern Emulators
In the authors' words
We study the fully-dynamic all-pairs minimum cut problem on planar graphs. Given an -vertex undirected planar graph undergoing edge insertions and deletions, the goal is to efficiently process these updates while supporting - minimum cut queries for any pair of vertices and . We give a -approximate dynamic algorithm that supports edge updates and minimum cut queries in time, for any . For general graphs, previous results either are limited to partially dynamic settings or achieve only logarithmic-factor approximations. The main conceptual and technical contribution is to show that a suitable adaptation of the planar emulator of Chang, Krauthgamer, and Tan~[STOC'22] satisfies the stronger pattern emulator introduced by Chen and Tan~[ICALP'25]. This leads almost immediately to a nearly linear-time construction of pattern emulators, which, when combined with the recent fully dynamic -approximate all-pairs shortest paths algorithm of Filtser, Goranci, Patel, and Probst Gutenberg~[FOCS'24], yields our result.
Appeared: Friday, October 30. arXiv. Preprint, not yet peer-reviewed.