Outerplanar Obstructions for Matroid Pathwidth

Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki

Research output: Contribution to journalArticlepeer-review


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.

Original languageEnglish (US)
Pages (from-to)541-546
Number of pages6
JournalElectronic Notes in Discrete Mathematics
StatePublished - Dec 1 2011


  • Linear-width
  • Matroid Pathwidth
  • Outerplanar Graphs
  • Pathwidth

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics


Dive into the research topics of 'Outerplanar Obstructions for Matroid Pathwidth'. Together they form a unique fingerprint.

Cite this