# Fully dynamic approximation schemes on planar and apex-minor-free graphs

arXiv: https://arxiv.org/abs/2310.20623 · HTML: https://mlsanity.com/paper/2310.20623/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Oct 2023.

## Built on by (most cited first, 1 of 1)

- [The Structural Complexity of Matrix-Vector Multiplication](https://mlsanity.com/paper/2502.21240/) (2025)

## Abstract (arXiv)

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: * maintain a (1-varepsilon)-approximation of the maximum weight of an independent set in G with amortized update time f(varepsilon)· no(1); and, * under the additional assumption that the maximum degree of the graph is bounded at all times by a constant, also maintain a (1+varepsilon)-approximation of the minimum weight of a dominating set in G with amortized update time f(varepsilon)· no(1). In both cases, f(varepsilon) is doubly-exponential in poly(1/varepsilon) and the data structure can be initialized in time f(varepsilon)· n1+o(1). All our results in fact hold in the larger generality of any graph class that excludes a fixed apex-graph as a minor.