Separating layered treewidth and row treewidth

Abstract

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.

References in corpus (6)

• Sparse universal graphs for planarity
• Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
• Notes on Graph Product Structure Theory
• New representation results for planar graphs
• Queue Layouts of Graphs with Bounded Degree and Bounded Genus
• Asymptotically Optimal Vertex Ranking of Planar Graphs

Cited by in corpus (3)

• Asymptotic Dimension of Minor-Closed Families and Assouad-Nagata Dimension of Surfaces
• Proper conflict-free list-coloring, odd minors, subdivisions, and layered treewidth
• Product structure of graphs with an excluded minor