Minor-Closed Graph Classes with Bounded Layered Pathwidth

2018/10/31 by Vida Dujmović, David Eppstein, Gwenaël Joret +2 · 1 citation
Computer Science · Mathematics · #1-planar graph #Advanced Graph Theory Research #Bounded function #Chordal graph #Class (philosophy) #Combinatorics #Complexity and Algorithms in Graphs #Computer science #Discrete mathematics #Graph #Humanities #Interconnection Networks and Systems #Line graph #Mathematics #Minor (academic) #Pathwidth #Treewidth #cs.DM #math.CO

paper · pdf · doi:10.1137/18m122162x

published as SIAM J. Discrete Math., 34(3), 1693-1709, 2020

openalex created_date 2018/10/26 · openalex publication_date 2020/01/01 · arxiv created 2020/06/04 · arxiv updated 2020/08/03 · openalex updated_date 2026/08/06

Abstract

We prove that a minor-closed class of graphs has bounded layered pathwidth if and only if some apex-forest is not in the class. This generalises a theorem of Robertson and Seymour, which says that a minor-closed class of graphs has bounded pathwidth if and only if some forest is not in the class.

Citations

• Parameterized Complexity Theory
• Local Tree-Width, Excluded Minors, and Approximation Algorithms
• Bidimensional Parameters and Local Treewidth
• Graph minors. I. Excluding a forest
• Graph Minors. XVI. Excluding a non-planar graph
• Graph minors. V. Excluding a planar graph
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A simple linear-time algorithm for finding path-decompositions of small width
• Diameter and Treewidth in Minor-Closed Graph Families
• Quickly excluding a forest
• Quickly Excluding a Planar Graph
• Nonrepetitive colorings of graphs of bounded tree-width
• Layout of Graphs with Bounded Tree-Width
• Polynomial Bounds for the Grid-Minor Theorem

Cited by

• Quickly excluding an annotated planar graph