  Graph separators are a ubiquitous tool in graph theory and computer science.
However, in some applications, their usefulness is limited by the fact that the
separator can be as large as $\Omega(\sqrt{n})$ in graphs with $n$ vertices.
This is the case for planar graphs, and more generally, for proper minor-closed
classes. We study a special type of graph separator, called a "layered
separator", which may have linear size in $n$, but has bounded size with
respect to a different measure, called the "width". We prove, for example, that
planar graphs and graphs of bounded Euler genus admit layered separators of
bounded width. More generally, we characterise the minor-closed classes that
admit layered separators of bounded width as those that exclude a fixed apex
graph as a minor.
  We use layered separators to prove $\mathcal{O}(\log n)$ bounds for a number
of problems where $\mathcal{O}(\sqrt{n})$ was a long-standing previous best
bound. This includes the nonrepetitive chromatic number and queue-number of
graphs with bounded Euler genus. We extend these results with a
$\mathcal{O}(\log n)$ bound on the nonrepetitive chromatic number of graphs
excluding a fixed topological minor, and a $\log^{ \mathcal{O}(1)}n$ bound on
the queue-number of graphs excluding a fixed minor. Only for planar graphs were
$\log^{ \mathcal{O}(1)}n$ bounds previously known. Our results imply that every
$n$-vertex graph excluding a fixed minor has a 3-dimensional grid drawing with
$n\log^{ \mathcal{O}(1)}n$ volume, whereas the previous best bound was
$\mathcal{O}(n^{3/2})$.
