Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
6423998 | Electronic Notes in Discrete Mathematics | 2011 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki,