  We establish relations between the bandwidth and the treewidth of bounded
degree graphs G, and relate these parameters to the size of a separator of G as
well as the size of an expanding subgraph of G. Our results imply that if one
of these parameters is sublinear in the number of vertices of G then so are all
the others. This implies for example that graphs of fixed genus have sublinear
bandwidth or, more generally, a corresponding result for graphs with any fixed
forbidden minor. As a consequence we establish a simple criterion for
universality for such classes of graphs and show for example that for each
gamma>0 every n-vertex graph with minimum degree ((3/4)+gamma)n contains a copy
of every bounded-degree planar graph on n vertices if n is sufficiently large.
