Separating layered treewidth and row treewidthArticle
Authors: Prosenjit Bose ; Vida Dujmović ; Mehrnoosh Javarsineh ; Pat Morin ; David R. Wood
NULL##NULL##NULL##NULL##NULL
Prosenjit Bose;Vida Dujmović;Mehrnoosh Javarsineh;Pat Morin;David R. Wood
Layered treewidth and row treewidth are recently introduced graph parameters
that have been key ingredients in the solution of several well-known open
problems. It follows from the definitions that the layered treewidth of a graph
is at most its row treewidth plus 1. Moreover, a minor-closed class has bounded
layered treewidth if and only if it has bounded row treewidth. However, it has
been open whether row treewidth is bounded by a function of layered treewidth.
This paper answers this question in the negative. In particular, for every
integer $k$ we describe a graph with layered treewidth 1 and row treewidth $k$.
We also prove an analogous result for layered pathwidth and row pathwidth.