Fully Dynamic All-Pairs Min Cuts on Planar Graphs via Planar Pattern Emulators

arXiv:2610.38730 · cs.DS · Submitted 2026-10-28 · Read on arXiv

cs.DS

Submitted: 2026-10-28

Updated: 2026-10-28

License: http://creativecommons.org/licenses/by/4.0/

The gist: We study the fully-dynamic all-pairs minimum cut problem on planar graphs.

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+ epsilon) -approximate dynamic algorithm that supports edge updates and minimum cut queries in n o(1) time, for any 1/poly(n) < epsilon < 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+ epsilon) -approximate all-pairs shortest paths algorithm of Filtser, Goranci, Patel, and Probst Gutenberg [FOCS'24], yields our result.

Related papers