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

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 -ε)-approximation of the maximum weight of an independent set in G with amortized update time f (ε) • n o(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 + ε)-approximation of the minimum weight of a dominating set in G with amortized update time f (ε) • n o(1) . In both cases, f (ε) is doubly-exponential in poly(1/ε) and the data structure can be initialized in time f (ε) • n 1+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.