A Unified Framework for Light Spanners

Seminal works on light spanners over the years provide spanners with optimal lightness in various graph classes, 1 such as in general graphs [17] , Euclidean spanners [26] and minor-free graphs [10] . Three shortcomings of previous works on light spanners are: (i) The runtimes of these constructions are almost always sub-optimal, and usually far from optimal. (ii) These constructions are optimal in the standard and crude sense, but not in a refined sense that takes into account a wider range of involved parameters. (iii) The techniques are ad hoc per graph class, and thus can't be applied broadly. This work aims at addressing these shortcomings by presenting a unified framework of light spanners in a variety of graph classes. Informally, the framework boils down to a transformation from sparse spanners to light spanners; since the state-of-the-art for sparse spanners is much more advanced than that for light spanners, such a transformation is powerful. First, we apply our framework to design fast constructions with optimal lightness for several graph classes. Among various applications, we highlight the following (for simplicity assume > 0 is fixed): • In low-dimensional Euclidean spaces, we present an O(n log n)-time construction of (1 + )spanners with lightness and degree both bounded by constants in the algebraic computation tree (ACT) (or real-RAM) model, which is the basic model used in Computational Geometry. The previous state-of-the-art runtime in this model for constant lightness (even for unbounded degree) was O(n log 2 n/ log log n), whereas O(n log n)-time spanner constructions with constant degree (and O(n) edges) are known for years. Our construction is optimal with respect to all the involved quality measures -runtime, lightness and degree -and it resolves a major problem in the area of geometric spanners, which was open for three decades (cf. [15, 3, 40, 53]). Second, we apply our framework to achieve more refined optimality bounds for several graph classes, i.e., the bounds remain optimal when taking into account a wider range of involved parameters, most notably . Our new constructions are significantly better than the state-of-the-art for every examined graph class. Among various applications, we highlight the following (now > 0 is any parameter): • For K r -minor-free graphs, we provide a (1 + )-spanner with lightness Õr, ( r + 1 2 ), where Õr, suppresses polylog factors of 1/ and r, improving the lightness bound Õr, ( r 3 ) of Borradaile, Le and Wulff-Nilsen [10] . We complement our upper bound with a highly nontrivial lower bound construction, for which any (1 + )-spanner must have lightness Ω( r + 1 2 ). Interestingly, our lower bound is realized by a geometric graph in R 2 . Also, the quadratic dependency on 1/ that we prove is surprising, as prior work suggested that the dependency on should be around 1/ . 1 The lightness is a normalized notion of weight: a graph's lightness is the ratio of its weight to the MST weight.