Layered separators in minor-closed graph classes with applications

We use layered separators to prove O(log⁡n) bounds for a number of problems where O(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 O(log⁡n) bound on the nonrepetitive chromatic number of graphs excluding a fixed topological minor, and a logO(1)⁡n bound on the queue-number of graphs excluding a fixed minor. Only for planar graphs were logO(1)⁡n bounds previously known. Our results imply that every n-vertex graph excluding a fixed minor has a 3-dimensional grid drawing with nlogO(1)⁡n volume, whereas the previous best bound was O(n3/2).