Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems
Eli Fox-Epstein, Philip N. Klein, Aaron Schild · Society for Industrial and Applied Mathematics eBooks · 2019
We show that, for any ∊ > 0, there is a deterministic embedding of edge-weighted planar graphs of diameter D into bounded-treewidth graphs. The embedding has additive error ∊D. We use this construction to obtain the first efficient bicriteria approximation schemes for weighted planar graphs addressing k-Center (equivalently d-Domination), and a metric generalization of independent set, d-independent SET. The approximation schemes employ a metric generalization of Baker's framework that is based on our embedding result.