2013/06/30 by Vida Dujmović, Pat Morin, David R. Wood · 2 citations
Mathematics · Computer Science · #math.CO #cs.CG #cs.DM
paper · pdf · doi:10.1016/j.jctb.2017.05.006
published as J. Combinatorial Theory Series B 127:111-147, 2017
arxiv created 2017/05/18 · arxiv updated 2018/06/21
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 classes. 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 "width". We prove, for example, that planar graphs and graphs of bounded Euler genus admit layered separators of bounded width. More generally, we characterise the minor-closed classes that admit layered separators of bounded width as those that exclude a fixed apex graph as a minor. 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 log O(1)n bound on the queue-number of graphs excluding a fixed minor. Only for planar graphs were log O(1)n bounds previously known. Our results imply that every n-vertex graph excluding a fixed minor has a 3-dimensional grid drawing with nlog O(1)n volume, whereas the previous best bound was O(n3/2).