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(√nlog² n). Equivalently, every n-vertex planar graph G has a set X of O(√nlog² n) vertices such that $G-X$ has bandwidth O(√nlog² n). This result holds in the more general setting of graphs contained in the strong product of a bounded treewidth graph and a path, which includes bounded genus graphs, graphs excluding a fixed apex graph as a minor, and k-planar graphs for fixed k. These results are obtained using two ingredients. The first is a new local sparsification lemma, which shows that every n-vertex planar graph G has a set of O((nlog n)/D) vertices whose removal results in a graph with local density at most D. The second is a generalization of a method of Feige and Rao, that relates bandwidth and local density using volume-preserving Euclidean embeddings.