Layered Separators in Minor-Closed Graph Classes with Applications

Abstract

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 $\Omega (\sqrt{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 $\mathcal{O}(\log n)$ bounds for a number of problems where $\mathcal{O}(\sqrt{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 $\mathcal{O}(\log n)$ bound on the nonrepetitive chromatic number of graphs excluding a fixed topological minor, and a ${\log }^{\mathcal{O}(1)}n$ bound on the queue-number of graphs excluding a fixed minor. Only for planar graphs were ${\log }^{\mathcal{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 $n{\log }^{\mathcal{O}(1)}n$ volume, whereas the previous best bound was $\mathcal{O}(n^{3/2})$.

References in corpus (3)

• New representation results for planar graphs
• List-coloring apex-minor-free graphs
• Thin graph classes and polynomial-time approximation schemes

Cited by in corpus (26)

• An annotated bibliography on 1-planarity
• Planar graphs have bounded queue-number
• A Survey on Graph Drawing Beyond Planarity
• Track Layouts, Layered Path Decompositions, and Leveled Planarity
• Planar graphs have bounded nonrepetitive chromatic number
• Clustered 3-Colouring Graphs of Bounded Degree
• Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
• Stack-number is not bounded by queue-number
• Clustered Graph Coloring and Layered Treewidth
• Minor-closed graph classes with bounded layered pathwidth
• Improved product structure for graphs on surfaces
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Asymptotic dimension of minor-closed families and beyond
• Separating layered treewidth and row treewidth
• Surfaces have (asymptotic) dimension 2
• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Product structure of graphs with an excluded minor
• Immersion and clustered coloring
• Orthogonal Tree Decompositions of Graphs
• Product structure extension of the Alon--Seymour--Thomas theorem
• Assouad-Nagata dimension of minor-closed metrics
• Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor
• Planar Graphs of Bounded Degree have Constant Queue Number
• Thickness and Antithickness of Graphs
• Book Embeddings of k-Map Graphs
• Weak diameter choosability of graphs with an excluded minor