Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring
Vida Dujmović, Pat Morin, David R. Wood · 2013
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 Ω(√n) in graphs with n vertices. This is the case for planar graphs, and more generally, for proper minor-closed families. 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 breadth. We prove that a wide class of graphs admit layered separators of bounded breadth, including graphs of bounded Euler genus. We use layered separators to prove Õ(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 to all proper minor-closed families, with a O(log n) bound on the nonrepetitive chromatic number, and a logO(1)n bound on the queue-number. Only for planar graphs were logO(1)n bounds previously known. Our results imply that every graph from a proper minor-closed class has a 3-dimensional grid drawing with n logO(1)n volume, whereas the previous best bound was O(n3/2). Readers interested in the full details should consult arXiv:1302.0304 and arXiv:1306.1595, rather than the current extended abstract.