Minor-Closed Graph Classes with Bounded Layered Pathwidth

DOI10.1137/18M122162XMaRDI QIDQ5130575zbMATH OpenOpenAlexFDO

Authors Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, David R. Wood

Publication date 28 October 2020

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

treewidthpathwidthgraph minorlayered pathwidthlayered treewidthapex-forest

Mathematics Subject Classification ID

Paths and cycles (05C38) Graph minors (05C83)

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.

Recommendations

• Layered separators in minor-closed graph classes with applications
• On the purity of minor-closed classes of graphs
• A Faster Shortest-Paths Algorithm for Minor-Closed Graph Classes
• Minimal classes of graphs of unbounded clique-width
• k -apices of Minor-closed Graph Classes. II. Parameterized Algorithms
• k-apices of minor-closed graph classes. I: Bounding the obstructions
• Long induced paths in minor-closed graph classes and beyond
• scientific article; zbMATH DE number 1439406
• Asymptotic properties of some minor-closed classes of graphs
• Asymptotic Properties of Some Minor-Closed Classes of Graphs

Cites work

• scientific article; zbMATH DE number 176762 (Why is no real title available?)
• scientific article; zbMATH DE number 2080088 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A simple linear-time algorithm for finding path-decompositions of small width
• Bidimensional Parameters and Local Treewidth
• Colouring planar graphs with three colours and no large monochromatic components
• Diameter and treewidth in minor-closed graph families
• Dividing a Graph into Triconnected Components
• Equivalence of local treewidth and linear local treewidth and its algorithmic applications
• Excluded grid theorem: improved and simplified
• Forcing a sparse minor
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Highly connected sets and the excluded grid theorem
• Layered separators in minor-closed graph classes with applications
• Layout of Graphs with Bounded Tree-Width
• Local tree-width, excluded minors, and approximation algorithms
• Nonrepetitive colorings of graphs of bounded tree-width
• On-Line Planarity Testing
• On-line maintenance of triconnected components with SPQR-trees
• Parametrized complexity theory.
• Polynomial bounds for the grid-minor theorem
• Quickly excluding a forest
• Quickly excluding a planar graph
• Structure of graphs with locally restricted crossings
• Towards tight(er) bounds for the excluded grid theorem
• Track layouts, layered path decompositions, and leveled planarity
• Tree-width and planar minors

Cited in

(7)

• Separating layered treewidth and row treewidth
• Clustered 3-colouring graphs of bounded degree
• The complexity of learning minor closed graph classes
• Long induced paths in minor-closed graph classes and beyond
• Cubic Planar Graphs that cannot be Drawn on few Lines
• Excluding a long double path minor
• Notes on graph product structure theory

This page was built for publication: Minor-Closed Graph Classes with Bounded Layered Pathwidth

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