Title: Minor-free graphs have light spanners,
Abstract: We show that every $H$-minor-free graph has a light $(1+\epsilon)$-spanner,
resolving an open problem of Grigni and Sissokho and proving a conjecture of
Grigni and Hung. Our lightness bound is
\[O\left(\frac{\sigma_H}{\epsilon^3}\log \frac{1}{\epsilon}\right)\] where
$\sigma_H = |V(H)|\sqrt{\log |V(H)|}$ is the sparsity coefficient of
$H$-minor-free graphs. That is, it has a practical dependency on the size of
the minor $H$. Our result also implies that the polynomial time approximation
scheme (PTAS) for the Travelling Salesperson Problem (TSP) in $H$-minor-free
graphs by Demaine, Hajiaghayi and Kawarabayashi is an efficient PTAS whose
running time is $2^{O_H\left(\frac{1}{\epsilon^4}\log
\frac{1}{\epsilon}\right)}n^{O(1)}$ where $O_H$ ignores dependencies on the
size of $H$. Our techniques significantly deviate from existing lines of
research on spanners for $H$-minor-free graphs, but build upon the work of
Chechik and Wulff-Nilsen for spanners of general graphs.