2020/08/24 by Hung Le, Le, Hung, Shay Solomon +1 · 3 citations
Computer Science · Engineering · #Advanced Graph Theory Research #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2008.10582
openalex publication_date 2020/08/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Seminal works on light spanners over the years have provided spanners with optimal lightness in various graph classes, such as general graphs, Euclidean spanners, and minor-free graphs. 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. 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.