Graphs of linear growth have bounded treewidth (Q6115513)
From MaRDI portal
scientific article; zbMATH DE number 7725117
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | Graphs of linear growth have bounded treewidth |
scientific article; zbMATH DE number 7725117 |
Statements
Graphs of linear growth have bounded treewidth (English)
0 references
10 August 2023
0 references
Summary: A graph class \(\mathcal{G}\) has linear growth if, for each graph \(G \in \mathcal{G}\) and every positive integer \(r\), every subgraph of \(G\) with radius at most \(r\) contains \(O(r)\) vertices. In this paper, we show that every graph class with linear growth has bounded treewidth.
0 references
tree-decomposition of a graph
0 references
\(k\)-stack layout
0 references
