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

<p>We prove that any graph excluding <em>K</em>_<em>r</em> as a minor has can be partitioned into clusters of diameter at most Δ while removing at most <em>O</em>(<em>r/</em>Δ) 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 <em>O</em>(<em>r</em>²/Δ) fraction of the edges. Our result is obtained by a new approach that relates 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 graphs excluding a fixed minor, can be used to construct padded decompositions of the metrics induced by such graphs. In particular, we get probabilistic partitions with padding parameter <em>O</em>(<em>r</em>) and strong-diameter partitions with padding parameter <em>O</em>(<em>r</em>²) for <em>K</em>_<em>r</em>-free graphs, <em>O</em>(<em>k</em>) for treewidth-<em>k</em> graphs, and <em>O</em>(log <em>g</em>) for graphs with genus <em>g</em>.</p>