Minor-Closed Graph Classes with Bounded Layered Pathwidth
Vida Dujmović, David Eppstein, Gwenaël Joret, Pat Morin, David R. Wood
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.
Topics & Concepts
MathematicsPathwidthBounded functionMinor (academic)CombinatoricsDiscrete mathematicsTreewidthClass (philosophy)1-planar graphGraphChordal graphLine graphComputer scienceHumanitiesPhilosophyArtificial intelligenceMathematical analysisAdvanced Graph Theory ResearchComplexity and Algorithms in GraphsInterconnection Networks and Systems