2025/05/30 by Hung Lê, Le, Hung, Shay Solomon +7 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph theory and applications
paper · pdf · doi:10.48550/arxiv.2505.24825
openalex publication_date 2025/05/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In their seminal paper, Althö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+ε)-spanner is at most (1+\frac2ε) ⋅ 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+ε)-spanner has a weight of at least (1+\frac2ε) ⋅ 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 ε)-spanner (for any 1≤ x = O(ε-1/2)) has a weight of Ω((1)/(ε⋅ x2))⋅ w(GOPT, ε), where GOPT, ε is a (1+ε)-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+ε⋅ 2O(log^* 1/ε))-spanner for G of total weight O(1)⋅ w(GOPT, ε). To achieve this result, we develop a new technique, which we refer to as \em iterative planar pruning. It iteratively modifies a spanner [...]