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 + ϵ)-spanner is at most (1

This bound is optimal in an existential sense: there exist planar graphs G for which any (1 + ϵ)-spanner has a weight of at least (1 + 2 ϵ ) • w(MST(G)). However, as an approximation algorithm, even for a 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ϵ)-spanner (for any 1

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

To achieve this result, we develop a new technique, which we refer to as iterative planar pruning. It iteratively modifies a spanner; each iteration replaces a heavy set of edges by a light path, to substantially decrease the total weight of the spanner while only slightly increasing its stretch. We leverage planarity to prove a laminar structural property of the edge set to be removed, which enables us to optimize the path to be inserted via dynamic programming. Our technique applies dynamic programming directly to the input planar graph, which significantly deviates from previous techniques used for network design problems in planar graphs, and might be of independent interest.