Outerplanar obstructions for matroid pathwidth

Athanassios Koutsonas; Dimitrios M. Thilikos; Koichi Yamazaki

doi:10.1016/j.disc.2013.10.007

Outerplanar obstructions for matroid pathwidth

Athanassios Koutsonas, Dimitrios M. Thilikos, Koichi Yamazaki

Computer Science

Research output: Contribution to journal › Article › peer-review

Abstract

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 language	English (US)
Pages (from-to)	95-101
Number of pages	7
Journal	Discrete Mathematics
Volume	315-316
Issue number	1
DOIs	https://doi.org/10.1016/j.disc.2013.10.007
State	Published - 2014

Keywords

Matroids
Obstructions
Outerplanar graphs
Pathwidth

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/j.disc.2013.10.007

Cite this

@article{b2ddfbf520404bf2be68a1cdedf4927a,

title = "Outerplanar obstructions for matroid pathwidth",

abstract = "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.",

keywords = "Matroids, Obstructions, Outerplanar graphs, Pathwidth",

author = "Athanassios Koutsonas and Thilikos, {Dimitrios M.} and Koichi Yamazaki",

year = "2014",

doi = "10.1016/j.disc.2013.10.007",

language = "English (US)",

volume = "315-316",

pages = "95--101",

journal = "Discrete Mathematics",

issn = "0012-365X",

publisher = "Elsevier B.V.",

number = "1",

}

TY - JOUR

T1 - Outerplanar obstructions for matroid pathwidth

AU - Koutsonas, Athanassios

AU - Thilikos, Dimitrios M.

AU - Yamazaki, Koichi

PY - 2014

Y1 - 2014

N2 - 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.

AB - 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.

KW - Matroids

KW - Obstructions

KW - Outerplanar graphs

KW - Pathwidth

UR - http://www.scopus.com/inward/record.url?scp=84887838250&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887838250&partnerID=8YFLogxK

U2 - 10.1016/j.disc.2013.10.007

DO - 10.1016/j.disc.2013.10.007

M3 - Article

AN - SCOPUS:84887838250

SN - 0012-365X

VL - 315-316

SP - 95

EP - 101

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

Outerplanar obstructions for matroid pathwidth

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this