Layered separators in minor-closed graph classes with applications

DOI10.1016/j.jctb.2017.05.006zbMath1371.05282arXiv1306.1595OpenAlexW2519651985MaRDI QIDQ2407382

David R. Wood, Pat Morin, 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

surfaceminorplanar graphseparatortopological minornonrepetitive colouringqueue layout3-dimensional grid drawinglayered separatorlayered treewidth

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)

Related Items

Smaller extended formulations for spanning tree polytopes in minor-closed classes and beyond ⋮ Clustered 3-colouring graphs of bounded degree ⋮ Parameterized Algorithms for Queue Layouts ⋮ Stack-number is not bounded by queue-number ⋮ An annotated bibliography on 1-planarity ⋮ Structure of Graphs with Locally Restricted Crossings ⋮ 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 ⋮ Long induced paths in minor-closed graph classes and beyond ⋮ Stack and Queue Layouts via Layered Separators ⋮ Graph product structure for non-minor-closed classes ⋮ Treewidth, Circle Graphs, and Circular Drawings ⋮ Minor-Closed Graph Classes with Bounded Layered Pathwidth ⋮ Graph layouts via layered separators ⋮ Orthogonal Tree Decompositions of Graphs ⋮ The degree-diameter problem for sparse graph classes ⋮ Track layouts, layered path decompositions, and leveled planarity ⋮ On the queue-number of graphs with bounded tree-width ⋮ Layouts of Expander Graphs ⋮ Representing graphs as the intersection of cographs and threshold graphs ⋮ Better bounds for poset dimension and boxicity ⋮ Notes on tree- and path-chromatic number ⋮ Planar Graphs of Bounded Degree Have Bounded Queue Number ⋮ Shorter Labeling Schemes for Planar Graphs ⋮ Immersion and clustered coloring ⋮ Parameterized Algorithms for Queue Layouts

Cites Work

• Expansion in SL\(_2(\mathbb R)\) and monotone expanders
• Crossings in grid drawings
• Clique minors in Cartesian products of graphs
• Sparsity. Graphs, structures, and algorithms
• Graph layouts via layered separators
• Nonrepetitive colouring via entropy compression
• Nonrepetitive vertex colorings of graphs
• Characterisations and examples of graph classes with bounded expansion
• Three-dimensional graph drawing
• Graph minors. III. Planar tree-width
• Nonrepetitive colorings of trees
• Nonrepetitive colorings of graphs -- a survey
• Thue type problems for graphs, points, and numbers
• Nonrepetitive colorings of graphs of bounded tree-width
• Volume requirements of 3D upward drawings
• Expanders and dimensional expansion
• Graph minors. V. Excluding a planar graph
• Embedding planar graphs in four pages
• S-functions for graphs
• Graph minors. XVI: Excluding a non-planar graph
• Diameter and treewidth in minor-closed graph families
• Diameter and treewidth in minor-closed graph families, revisited
• Graph minor hierarchies
• Nonrepetitive colourings of planar graphs with \(O(\log n)\) colours
• Planar decompositions and the crossing number of graphs with an excluded minor
• Local tree-width, excluded minors, and approximation algorithms
• Upward three-dimensional grid drawings of graphs
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Spanning trees of dual graphs
• Über eine Eigenschaft der ebenen Komplexe
• Spanning subgraphs of embedded graphs
• A separator theorem for graphs of bounded genus
• The cycle space of an embedded graph
• Layouts of Expander Graphs
• On square-free vertex colorings of graphs
• Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs
• Graph minors. II. Algorithmic aspects of tree-width
• A Separator Theorem for Planar Graphs
• A Separator Theorem for Nonplanar Graphs
• Laying Out Graphs Using Queues
• Comparing Queues and Stacks As Machines for Laying Out Graphs
• Approximation algorithms for NP-complete problems on planar graphs
• Genus g Graphs Have Pagenumber O(√g)
• Subgraph Isomorphism in Planar Graphs and Related Problems
• Thin graph classes and polynomial-time approximation schemes
• The Maximum Number of Edges in a Three-Dimensional Grid-Drawing
• Nonrepetitive colorings of graphs
• Linear Algorithms for Partitioning Embedded Graphs of Bounded Genus
• Structure Theorem and Isomorphism Test for Graphs with Excluded Topological Subgraphs
• Layout of Graphs with Bounded Tree-Width
• Bidimensional Parameters and Local Treewidth
• Structure of Graphs with Locally Restricted Crossings
• On the Queue Number of Planar Graphs
• A note on primitive skew curves
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item