  Given a metric space $(X,d_X)$, a $(\beta,s,\Delta)$-sparse cover is a
collection of clusters $\mathcal{C}\subseteq P(X)$ with diameter at most
$\Delta$, such that for every point $x\in X$, the ball
$B_X(x,\frac\Delta\beta)$ is fully contained in some cluster $C\in
\mathcal{C}$, and $x$ belongs to at most $s$ clusters in $\mathcal{C}$. Our
main contribution is to show that the shortest path metric of every $K_r$-minor
free graphs admits $(O(r),O(r^2),\Delta)$-sparse cover, and for every
$\epsilon>0$, $(4+\epsilon,O(\frac1\epsilon)^r,\Delta)$-sparse cover (for
arbitrary $\Delta>0$). We then use this sparse cover to show that every
$K_r$-minor free graph embeds into
$\ell_\infty^{\tilde{O}(\frac1\epsilon)^{r+1}\cdot\log n}$ with distortion
$3+\eps$ (resp. into $\ell_\infty^{\tilde{O}(r^2)\cdot\log n}$ with distortion
$O(r)$). Further, we provide applications of these sparse covers into padded
decompositions, sparse partitions, universal TSP / Steiner tree, oblivious buy
at bulk, name independent routing, and path reporting distance oracles.
