Outerplanar obstructions for matroid pathwidth

Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki

Research output: Contribution to journalArticlepeer-review


For each non-negative integer 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)95-101
Number of pages7
JournalDiscrete Mathematics
Issue number1
StatePublished - 2014


  • Matroids
  • Obstructions
  • Outerplanar graphs
  • Pathwidth

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Outerplanar obstructions for matroid pathwidth'. Together they form a unique fingerprint.

Cite this