Minor-Closed Graph Classes with Bounded Layered Pathwidth

DOI10.1137/18M122162XzbMath1450.05086arXiv1810.08314OpenAlexW2897886958MaRDI QIDQ5130575

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

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

treewidthgraph minorpathwidthlayered pathwidthlayered treewidthapex-forest

Mathematics Subject Classification ID

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

Related Items (4)

Clustered 3-colouring graphs of bounded degree ⋮ Separating layered treewidth and row treewidth ⋮ Cubic Planar Graphs that cannot be Drawn on few Lines ⋮ Notes on graph product structure theory

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A simple linear-time algorithm for finding path-decompositions of small width
• Nonrepetitive colorings of graphs of bounded tree-width
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• Quickly excluding a forest
• Highly connected sets and the excluded grid theorem
• Quickly excluding a planar graph
• Graph minors. XVI: Excluding a non-planar graph
• Diameter and treewidth in minor-closed graph families
• Track layouts, layered path decompositions, and leveled planarity
• On-line maintenance of triconnected components with SPQR-trees
• Tree-width and planar minors
• Layered separators in minor-closed graph classes with applications
• Parametrized complexity theory.
• Local tree-width, excluded minors, and approximation algorithms
• Excluded Grid Theorem
• Polynomial Bounds for the Grid-Minor Theorem
• On-Line Planarity Testing
• Dividing a Graph into Triconnected Components
• Towards Tight(er) Bounds for the Excluded Grid Theorem
• Layout of Graphs with Bounded Tree-Width
• Bidimensional Parameters and Local Treewidth
• Structure of Graphs with Locally Restricted Crossings
• Forcing a sparse minor
• Colouring Planar Graphs With Three Colours and No Large Monochromatic Components
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

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