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 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 to all proper minor-closed families, with a O(log n) bound on the nonrepetitive chromatic number, and a log O(1) n bound on the queue-number. Only for planar graphs were log O(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 O(1) n volume, whereas the previous best bound was O(n 3/2). Readers interested in the full details should consult arXiv:1302.0304 and arXiv:1306.1595, rather than the current extended abstract. Copyright

Additional Metadata
Keywords Graph, Graph drawing, Minor, Nonrepetitive colouring, Queue layout, Separator, Track layout
Persistent URL
Conference 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Dujmović, V, Morin, P, & Wood, D. (2013). Layered separators for queue layouts, 3D graph drawing and nonrepetitive coloring. Presented at the 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013. doi:10.1109/FOCS.2013.38