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 dx.doi.org/10.1109/FOCS.2013.38
Conference 2013 IEEE 54th Annual Symposium on Foundations of Computer Science, FOCS 2013
Citation
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