Pith. sign in

Notes on Graph Product Structure Theory

1 Pith paper cite this work. Polarity classification is still indexing.

1 Pith paper citing it
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

background 1

citation-polarity summary

fields

math.CO 1

years

2026 1

verdicts

ACCEPT 1

roles

background 1

polarities

background 1

representative citing papers

Row pathwidth of complete binary trees

math.CO · 2026-08-10 · accept · novelty 8.0

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.

citing papers explorer

Showing 1 of 1 citing paper.

  • Row pathwidth of complete binary trees math.CO · 2026-08-10 · accept · none · ref 3 · internal anchor

    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.