The structure of obstructions to treewidth and pathwidth

DOI10.1016/S0166-218X(01)00281-5zbMath1001.05102MaRDI QIDQ1613365

Janka Chlebíková

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

structural characterizationtreewidthpathwidthobstruction set

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75)

Related Items (6)

Graph Minors and Parameterized Algorithm Design ⋮ Sparse obstructions for minor-covering parameters ⋮ Achievable sets, brambles, and sparse treewidth obstructions ⋮ Confronting intractability via parameters ⋮ Minor obstructions for apex-pseudoforests ⋮ On sparsification for computing treewidth

Cites Work

• Unnamed Item
• Unnamed Item
• Forbidden minors characterization of partial 3-trees
• The vertex separation number of a graph equals its path-width
• Obstruction set isolation for the gate matrix layout problem
• Graph minors. XIII: The disjoint paths problem
• The Structure and Number of Obstructions to Treewidth
• Representation of a finite graph by a set of intervals on the real line
• A characterization of partial 3-trees
• On Linear Recognition of Tree-Width at Most Four
• A Characterization of Comparability Graphs and of Interval Graphs

This page was built for publication: The structure of obstructions to treewidth and pathwidth