TY - JOUR

T1 - Characterizing width two for variants of treewidth

AU - Bodlaender, H.L.

AU - Kratsch, S.

AU - Kreuzen, V.J.C.

AU - Kwon, O.-J.

AU - Ok, S.

PY - 2017/1/10

Y1 - 2017/1/10

N2 - In this paper, we consider the notion of special treewidth , recently introduced by Courcelle (2012). In a special tree decomposition, for each vertex vv in a given graph, the bags containing vv form a rooted path. We show that the class of graphs of special treewidth at most two is closed under taking minors, and give the complete list of the six minor obstructions. As an intermediate result, we prove that every connected graph of special treewidth at most two can be constructed by arranging blocks of special treewidth at most two in a specific tree-like fashion.
Inspired by the notion of special treewidth, we introduce three natural variants of treewidth, namely spaghetti treewidth, strongly chordal treewidth and directed spaghetti treewidth. All these parameters lie between pathwidth and treewidth, and we provide common structural properties on these parameters. For each parameter, we prove that the class of graphs having the parameter at most two is minor closed, and we characterize those classes in terms of a tree of cycles with additional conditions. Finally, we show that for each k=3k=3, the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most kk, is not closed under taking minors.
Keywords: Treewidth; Special treewidth; Spaghetti treewidth; Strongly chordal treewidth; Minor

AB - In this paper, we consider the notion of special treewidth , recently introduced by Courcelle (2012). In a special tree decomposition, for each vertex vv in a given graph, the bags containing vv form a rooted path. We show that the class of graphs of special treewidth at most two is closed under taking minors, and give the complete list of the six minor obstructions. As an intermediate result, we prove that every connected graph of special treewidth at most two can be constructed by arranging blocks of special treewidth at most two in a specific tree-like fashion.
Inspired by the notion of special treewidth, we introduce three natural variants of treewidth, namely spaghetti treewidth, strongly chordal treewidth and directed spaghetti treewidth. All these parameters lie between pathwidth and treewidth, and we provide common structural properties on these parameters. For each parameter, we prove that the class of graphs having the parameter at most two is minor closed, and we characterize those classes in terms of a tree of cycles with additional conditions. Finally, we show that for each k=3k=3, the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most kk, is not closed under taking minors.
Keywords: Treewidth; Special treewidth; Spaghetti treewidth; Strongly chordal treewidth; Minor

KW - Minor

KW - Spaghetti treewidth

KW - Special treewidth

KW - Strongly chordal treewidth

KW - Treewidth

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

U2 - 10.1016/j.dam.2015.01.015

DO - 10.1016/j.dam.2015.01.015

M3 - Article

VL - 216

SP - 29

EP - 46

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

SN - 0166-218X

IS - Part 1

ER -