The row pathwidth of the height-h complete binary tree is at least floor((h+1)/16), so it grows linearly with h and matches the general upper bound up to constants.
Notes on Graph Product Structure Theory
1 Pith paper cite this work. Polarity classification is still indexing.
abstract
It was recently proved that every planar graph is a subgraph of the strong product of a path and a graph with bounded treewidth. This paper surveys generalisations of this result for graphs on surfaces, minor-closed classes, various non-minor-closed classes, and graph classes with polynomial growth. We then explore how graph product structure might be applicable to more broadly defined graph classes. In particular, we characterise when a graph class defined by a cartesian or strong product has bounded or polynomial expansion. We then explore graph product structure theorems for various geometrically defined graph classes, and present several open problems.
citation-role summary
citation-polarity summary
fields
math.CO 1years
2026 1verdicts
ACCEPT 1roles
background 1polarities
background 1representative citing papers
citing papers explorer
-
Row pathwidth of complete binary trees
The row pathwidth of the height-h complete binary tree is at least floor((h+1)/16), so it grows linearly with h and matches the general upper bound up to constants.