Planar graphs in blowups of fans

We show that every n-vertex planar graph is contained in the graph obtained from a fan by blowing up each vertex by a complete graph of order O(√(n log² n)). Equivalently, every n-vertex planar graph G has a set X of O(√(n log² n)) vertices such that G−X has bandwidth O(√(n log² n)). We in fact prove the same result for any proper minor-closed class, and we prove more general results that explore the trade-off between X and the bandwidth of G−X. The proofs use three key ingredients. The first is a new local sparsification lemma, which shows that every n-vertex planar graph G has a set of O((n log n)/δ) vertices whose removal results in a graph with local density at most δ. The second is a generalization of a method of Feige and Rao that relates bandwidth and local density using volume-preserving Euclidean embeddings. The third ingredient is graph products, which are a key tool in the extension to any proper minor-closed class.