Embedding Planar Graphs into Low-Treewidth Graphs with Applications to Efficient Approximation Schemes for Metric Problems

摘要

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.