Multiplicative Spanners in Minor-Free Graphs

In FOCS 2017, Borradaille, Le, and Wulff-Nilsen addressed a long-standing open problem by proving that minor-free graphs have light spanners. Specifically, they proved that every $K_h$-minor-free graph has a $(1+\epsilon )$-spanner of lightness $O_{\epsilon }(h\sqrt{\log h})$, hence constant when $h$ and $\epsilon$ are regarded as constants. We extend this result by showing that a more expressive size/stretch tradeoff is available. Specifically: for any positive integer $k$, every $n$-node, $K_h$-minor-free graph has a $(2k-1)$-spanner with sparsity $$O(h^{\frac{2}{k+1}}\cdot \text{polylog }h),$$ and a $(1+\epsilon )(2k-1)$-spanner with lightness $$O_{\epsilon }(h^{\frac{2}{k+1}}\cdot \text{polylog }h)\mathrm{.}$$ We further prove that this exponent $\frac{2}{k+1}$ is best possible, assuming the girth conjecture. At a technical level, our proofs leverage the recent improvements by Postle (2020) to the remarkable density increment theorem for minor-free graphs.