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
    0 references
    0 references
    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

    Identifiers

    0 references
    0 references
    0 references
    0 references