Approximate Light Spanners in Planar Graphs

In their seminal paper, Althöfer et al. (DCG 1993) introduced the greedy spanner and showed that, for any weighted planar graph \(G\), the weight of the greedy \((1+\epsilon)\)-spanner is at most \((1+\tfrac{2}{\epsilon})\cdot \textrm w(\mathsf{MST}(G))\), where \(\textrm w(\mathsf{MST}(G))\) is the weight of a minimum spanning tree \(\mathrm{MST}(G)\) of \(G\). This bound is optimal in an \(\textcolor{#ff6666}{existential\ sense}\): there exist planar graphs \(G\) for which any \((1+\epsilon)\)-spanner has a weight of at least \((1+\tfrac{2}{\epsilon})\cdot w(\mathrm{MST}(G))\).