An improved planar graph product structure theorem (Q2152790)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improved planar graph product structure theorem |
scientific article |
Statements
An improved planar graph product structure theorem (English)
0 references
11 July 2022
0 references
Summary: \textit{V. Dujmović} et al. [J. ACM 67, No. 4, Article No. 22, 38 p. (2020; Zbl 1466.05047)] proved that for every planar graph \(G\) there is a graph \(H\) with treewidth at most 8 and a path \(P\) such that \(G\subseteq H\boxtimes P\). We improve this result by replacing ``treewidth at most 8'' by ``simple treewidth at most 6''.
0 references