An improved planar graph product structure theorem (Q2152790)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: An improved planar graph product structure theorem |
scientific article; zbMATH DE number 7555136
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | An improved planar graph product structure theorem |
scientific article; zbMATH DE number 7555136 |
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
0.84101236
0 references
0.81013983
0 references
0.7986213
0 references
0 references
0.72414935
0 references
0 references
0 references
0.69976014
0 references
0.6993521
0 references
