1. Outerplanar Obstructions for Matroid Pathwidth.
- Author
-
Koutsonas, Athanassios, Thilikos, Dimitrios M., and Yamazaki, Koichi
- Subjects
GRAPH theory ,MATROIDS ,PATHS & cycles in graph theory ,MATHEMATICAL decomposition ,EXISTENCE theorems ,MATHEMATICAL analysis ,COMBINATORICS - Abstract
Abstract: For each k, we provide all outerplanar obstructions for the class of graphs whose cycle matroid has pathwidth at most k. Our proof combines a decomposition lemma for proving lower bounds on matroid pathwidth and a relation between matroid pathwidth and linear-width. Our results imply the existence of a linear algorithm that, given an outerplanar graph, outputs its matroid pathwidth. [Copyright &y& Elsevier]
- Published
- 2011
- Full Text
- View/download PDF