Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4949881 | Discrete Applied Mathematics | 2017 | 18 Pages |
Abstract
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â¥3, the class of graphs with special treewidth, spaghetti treewidth, directed spaghetti treewidth, or strongly chordal treewidth, respectively at most k, is not closed under taking minors.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Hans L. Bodlaender, Stefan Kratsch, Vincent J.C. Kreuzen, O-joung Kwon, Seongmin Ok,