Title: Cops, Robbers, and Threatening Skeletons:  Padded Decomposition for Minor-Free Graphs.

Authors: Ittai Abraham, Cyril Gavoille, Anupam Gupta, Ofer Neiman and Kunal Talwar.

Abstract: 

We prove that any graph excluding $K_r$ as a minor has can be partitioned into clusters of diameter 
at most $\Delta$ while removing at most $O(r/\Delta)$ fraction of the edges. This improves over the 
results of Fakcharoenphol and Talwar, who building on the work of Klein, Plotkin and Rao gave a partitioning 
that required to remove $O(r^2/\Delta)$  fraction of the edges.

Our result is obtained by a new approach to relate the topological
properties (excluding a minor) of a graph to its geometric properties
(the induced shortest path metric). Specifically, we show that
techniques used by Andreae in his investigation of the cops-and-robbers
game on excluded-minor graphs can be used to construct padded
decompositions of the metrics induced by such graphs. In particular, we
get probabilistic partitions with padding parameter $O(r)$ and
strong-diameter partitions with padding parameter $O(r^2)$ for
$K_r$-free graphs, padding $O(k)$ for graphs with treewidth
$k$, and padding $O(\log g)$ for graphs with genus $g$.