In their seminal paper, Alth\"{ o}fer et al. (DCG 1993) introduced the { \em greedy spanner} and showed that, for any weighted planar graph $G$, the weight of the greedy $(1+\epsilon)$-spanner is at most $(1+\frac{ 2}{ \epsilon}) \cdot w(MST(G))$, where $w(MST(G))$ is the weight of a minimum spanning tree $MST(G)$ of $G$. This bound is optimal in an { \em existential sense}: there exist planar graphs $G$ for which any $(1+\epsilon)$-spanner has a weight of at least $(1+\frac{ 2}{ \epsilon}) \cdot w(MST(G))$. However, as an { \em approximation algorithm}, even for a { \em bicriteria} approximation, the weight approximation factor of the greedy spanner is essentially as large as the existential bound: There exist planar graphs $G$ for which the greedy $(1+x \epsilon)$-spanner (for any $1\leq x = O(\epsilon^{ -1/2})$) has a weight of $\Omega(\frac{ 1}{ \epsilon \cdot x^2})\cdot w(G_{ OPT, \epsilon})$, where $G_{ OPT, \epsilon}$ is a $(1+\epsilon)$-spanner of $G$ of minimum weight. Despite the flurry of works over the past three decades on approximation algorithms for spanners as well as on light(-weight) spanners, there is still no (possibly bicriteria) approximation algorithm for light spanners in weighted planar graphs that outperforms the existential bound. As our main contribution, we present a polynomial time algorithm for constructing, in any weighted planar graph $G$, a $(1+\epsilon\cdot 2^{ O(\log^* 1/\epsilon)})$-spanner for $G$ of total weight $O(1)\cdot w(G_{ OPT, \epsilon})$. To achieve this result, we develop a new technique, which we refer to as { \em iterative planar pruning}. It iteratively modifies a spanner [...]
Categories: cs.DS