Fully dynamic approximation schemes on planar and apex-minor-free graphs
Tuukka Korhonen, Wojciech Nadara, Michał Pilipczuk, Marek Sokołowski · Society for Industrial and Applied Mathematics eBooks · 2024
The classic technique of Baker [J. ACM ‘94] is the most fundamental approach for designing approximation schemes on planar, or more generally topologically-constrained graphs, and it has been applied in a myriad of different variants and settings throughout the last 30 years. In this work we propose a dynamic variant of Baker's technique, where instead of finding an approximate solution in a given static graph, the task is to design a data structure for maintaining an approximate solution in a fully dynamic graph, that is, a graph that is changing over time by edge deletions and edge insertions. Specifically, we address the two most basic problems — Maximum Weight Independent Set and Minimum Weight Dominating Set — and we prove the following: for a fully dynamic n-vertex planar graph G, one can