Dynamic planar graph method speeds up all-pairs minimum cut queries
Fully Dynamic All-Pairs Min Cuts on Planar Graphs via Planar Pattern Emulators
Data Structures and Algorithms
Summary
This paper deals with finding the smallest way to separate any two points in a special type of network called a planar graph, even as connections are added or removed. The authors develop a new fast algorithm that gives answers close to exact in very little time. They use a special tool called planar pattern emulators to keep track of these separations efficiently. This approach improves on previous methods that either worked slower or only in limited scenarios.
What this means in practice
- •For network engineers: Maintain fast approximate connectivity checks between any two points in planar network topologies that change over time.
- •For geographic information system developers: Enable efficient updates and queries on planar maps representing roads or utilities as routes or connections are modified.
Authors
Arnold Filtser, Gramoz Goranci, Ali Momeni, Neel Patel, Maximilian Probst Gutenberg
Abstract
We study the fully-dynamic all-pairs minimum cut problem on planar graphs. Given an $n$-vertex undirected planar graph $G=(V,E)$ undergoing edge insertions and deletions, the goal is to efficiently process these updates while supporting $s$-$t$ minimum cut queries for any pair of vertices $s$ and $t$. We give a $(1+\varepsilon)$-approximate dynamic algorithm that supports edge updates and minimum cut queries in $n^{o(1)}$ time, for any $1/\text{poly}(\log n) < \varepsilon < 1$. 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 $(1+\varepsilon)$-approximate all-pairs shortest paths algorithm of Filtser, Goranci, Patel, and Probst Gutenberg~[FOCS'24], yields our result.