Layered Separators for Queue Layouts, 3D Graph Drawing and Nonrepetitive Coloring

摘要

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 logmathcalO(1)n bound on the queue-number. Only for planar graphs were log mathcalO(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 log mathcalO(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.