Bandwidth, treewidth, separators, expansion, and universality

We prove that planar graphs with bounded maximum degree have sublinear bandwidth. As a consequence for each γ > 0 every n-vertex graph with minimum degree ( 3 4 + γ ) n contains a copy of every bounded-degree planar graph on n vertices. The proof relies on the fact that planar graphs have small separators. Indeed, we show more generally that for any class of bounded-degree graphs the concepts of sublinear bandwidth, sublinear treewidth, the absence of big expanders as subgraphs, and the existence of small separators are equivalent.