Layered separators in minor-closed graph classes with applications

DOI10.1016/J.JCTB.2017.05.006MaRDI QIDQ2407382zbMATH OpenOpenAlexFDO

Authors Pat Morin, David R. Wood, Vida Dujmović

Publication date 29 September 2017

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1306.1595

zbMATH Keywords

3-dimensional grid drawinglayered separatorlayered treewidthminornonrepetitive colouringplanar graphqueue layoutseparatorsurfacetopological minor

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

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(sqrtn)$ 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 $mathcalO(logn)$ bounds for a number of problems where $mathcalO(sqrtn)$ 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 $mathcalO(logn)$ bound on the nonrepetitive chromatic number of graphs excluding a fixed topological minor, and a $lo{g}^{mathcalO(1)}n$ bound on the queue-number of graphs excluding a fixed minor. Only for planar graphs were $lo{g}^{mathcalO(1)}n$ bounds previously known. Our results imply that every $n$-vertex graph excluding a fixed minor has a 3-dimensional grid drawing with $nlo{g}^{mathcalO(1)}n$ volume, whereas the previous best bound was $mathcalO(n^{3/2})$.

Recommendations

• Planar graphs have bounded queue-number
• Graph layouts via layered separators
• Edge separators for graphs of bounded genus with applications

Cites work

• A note on primitive skew curves
• A separator theorem for graphs of bounded genus
• A Separator Theorem for Nonplanar Graphs
• A Separator Theorem for Planar Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
• Bidimensional Parameters and Local Treewidth
• Bounded-degree graphs have arbitrarily large queue-number
• Characterisations and examples of graph classes with bounded expansion
• Clique minors in Cartesian products of graphs
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Crossings in grid drawings
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Embedding planar graphs in four pages
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Expanders and dimensional expansion
• Expansion in SL₂( R) and monotone expanders
• Genus g Graphs Have Pagenumber O(√g)
• Graph layouts via layered separators
• Graph minor hierarchies
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. III. Planar tree-width
• Graph minors. V. Excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Graphs on surfaces
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• scientific article; zbMATH DE number 2084287 (Why is no real title available?)
• scientific article; zbMATH DE number 53949 (Why is no real title available?)
• scientific article; zbMATH DE number 3480514 (Why is no real title available?)
• scientific article; zbMATH DE number 4127226 (Why is no real title available?)
• scientific article; zbMATH DE number 1241845 (Why is no real title available?)
• scientific article; zbMATH DE number 475621 (Why is no real title available?)
• scientific article; zbMATH DE number 1057879 (Why is no real title available?)
• scientific article; zbMATH DE number 2079390 (Why is no real title available?)
• scientific article; zbMATH DE number 2145229 (Why is no real title available?)
• scientific article; zbMATH DE number 2159644 (Why is no real title available?)
• scientific article; zbMATH DE number 2159655 (Why is no real title available?)
• Laying Out Graphs Using Queues
• Layout of Graphs with Bounded Tree-Width
• Layouts of Expander Graphs
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• Local tree-width, excluded minors, and approximation algorithms
• Monotone expanders: constructions and applications
• Neochromatica.
• Nonrepetitive colorings of graphs
• Nonrepetitive colorings of graphs -- a survey
• Nonrepetitive colorings of graphs of bounded tree-width
• Nonrepetitive colorings of trees
• Nonrepetitive colouring via entropy compression
• Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
• Nonrepetitive vertex colorings of graphs
• On square-free vertex colorings of graphs
• On the Queue Number of Planar Graphs
• Planar decompositions and the crossing number of graphs with an excluded minor
• Queue layouts of graph products and powers
• S-functions for graphs
• Spanning subgraphs of embedded graphs
• Spanning trees of dual graphs
• Sparsity. Graphs, structures, and algorithms
• Stacks, queues and tracks: layouts of graph subdivisions
• Structure of graphs with locally restricted crossings
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs
• Subgraph Isomorphism in Planar Graphs and Related Problems
• The cycle space of an embedded graph
• The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
• Thin graph classes and polynomial-time approximation schemes
• Three-dimensional graph drawing
• Thue type problems for graphs, points, and numbers
• Upward three-dimensional grid drawings of graphs
• Volume requirements of 3D upward drawings
• Über eine Eigenschaft der ebenen Komplexe

Cited in

(45)

• Track layouts, layered path decompositions, and leveled planarity
• Representing graphs as the intersection of cographs and threshold graphs
• Notes on tree- and path-chromatic number
• Immersion and clustered coloring
• Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond
• Stack-number is not bounded by queue-number
• An annotated bibliography on 1-planarity
• Long induced paths in minor-closed graph classes and beyond
• Layouts of Expander Graphs
• Orthogonal tree decompositions of graphs
• Graph layouts via layered separators
• The degree-diameter problem for sparse graph classes
• Parameterized Algorithms for Queue Layouts
• Parameterized algorithms for queue layouts
• Minor-Closed Graph Classes with Bounded Layered Pathwidth
• On the queue-number of graphs with bounded tree-width
• Better bounds for poset dimension and boxicity
• Planar graphs of bounded degree have bounded queue number
• Structure of graphs with locally restricted crossings
• Shorter Labeling Schemes for Planar Graphs
• Clustered 3-colouring graphs of bounded degree
• Separating layered treewidth and row treewidth
• Improved product structure for graphs on surfaces
• Spined categories: generalizing tree-width beyond graphs
• Book embeddings of \(k\)-framed graphs and \(k\)-map graphs
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• Graph product structure for non-minor-closed classes
• Treewidth, Circle Graphs, and Circular Drawings
• Product structure extension of the Alon-Seymour-Thomas theorem
• Asymptotic dimension of minor-closed families and Assouad-Nagata dimension of surfaces
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Treewidth, circle graphs and circular drawings
• Product structure of graphs with an excluded minor
• Cop-width, flip-width and strong colouring numbers
• Induced minors and region intersection graphs
• On the complexity of embedding in graph products
• Intersection graphs with and without product structure
• Product structure of graph classes with strongly sublinear separators
• Weak diameter choosability of graphs with an excluded minor
• Grid minors and products
• Assouad-Nagata dimension of minor-closed metrics
• Powers of planar graphs, product structure, and blocking partitions
• Twin-width of graphs on surfaces
• Clustered coloring of graphs excluding a subgraph and a minor
• Layer-based width for \textbf{PAFP} on DAGs: a BFS-width-2 normal form and exact-length width-2 tractability

This page was built for publication: Layered separators in minor-closed graph classes with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2407382)