Graphs of linear growth have bounded treewidth (Q6115513): Difference between revisions

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

Mathematics Subject Classification ID

05C83

0 references

0 references

0 references

tree-decomposition of a graph

0 references

\(k\)-stack layout

0 references

MaRDI profile type

MaRDI publication profile

0 references

OpenAlex ID

W4384339936

0 references

cites work

Growth and percolation on the uniform infinite planar triangulation

0 references

The book thickness of 1-planar graphs is constant

0 references

Four pages are indeed necessary for planar graphs

0 references

A partial k-arboretum of graphs with bounded treewidth

0 references

Linearity of grid minors in treewidth with applications through bidimensionality

0 references

Some results on tree decomposition of graphs

0 references

Stack-number is not bounded by queue-number

0 references

Graph treewidth and geometric thickness parameters

0 references

Treewidth of graphs with balanced separations

0 references

On planar graphs of uniform polynomial growth

0 references

The pagenumber of \(k\)-trees is \(O(k)\)

0 references

A note on bounded automorphisms of infinite graphs

0 references

Graphs with polynomial growth are covering graphs

0 references

Q4011119

0 references

On tree width, bramble size, and expansion

0 references

Groups of polynomial growth and expanding maps. Appendix by Jacques Tits

0 references

Q3772406

0 references

Parameters Tied to Treewidth

0 references

A bound for groups of linear growth

0 references

A note on the growth of transitive graphs

0 references

A survey on graphs with polynomial growth

0 references

Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor

0 references

The intrinsic dimensionality of graphs

0 references

Logical aspects of Cayley-graphs: the group case

0 references

Constant-degree graph expansions that preserve treewidth

0 references

Growth of finitely generated solvable groups

0 references

Q4407447

0 references

Graph minors. II. Algorithmic aspects of tree-width

0 references

Graph minors. V. Excluding a planar graph

0 references

Quickly excluding a planar graph

0 references

Q3150763

0 references

Q3491608

0 references

Q3340884

0 references

Growth of finitely generated solvable groups and curvature of Riemannian manifolds

0 references

On tree-partition-width

0 references

Embedding planar graphs in four pages

0 references

Planar graphs that need four pages

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:6115513

@@ Property / cites work @@
+Growth and percolation on the uniform infinite planar triangulation
+Normal rank
@@ Property / cites work @@
+The book thickness of 1-planar graphs is constant
@@ Property / cites work: The book thickness of 1-planar graphs is constant / rank @@
+Normal rank
@@ Property / cites work @@
+Four pages are indeed necessary for planar graphs
@@ Property / cites work: Four pages are indeed necessary for planar graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A partial k-arboretum of graphs with bounded treewidth
+Normal rank
@@ Property / cites work @@
+Linearity of grid minors in treewidth with applications through bidimensionality
+Normal rank
@@ Property / cites work @@
+Some results on tree decomposition of graphs
@@ Property / cites work: Some results on tree decomposition of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Stack-number is not bounded by queue-number
@@ Property / cites work: Stack-number is not bounded by queue-number / rank @@
+Normal rank
@@ Property / cites work @@
+Graph treewidth and geometric thickness parameters
+Normal rank
@@ Property / cites work @@
+Treewidth of graphs with balanced separations
@@ Property / cites work: Treewidth of graphs with balanced separations / rank @@
+Normal rank
@@ Property / cites work @@
+On planar graphs of uniform polynomial growth
@@ Property / cites work: On planar graphs of uniform polynomial growth / rank @@
+Normal rank
@@ Property / cites work @@
+The pagenumber of \(k\)-trees is \(O(k)\)
@@ Property / cites work: The pagenumber of \(k\)-trees is \(O(k)\) / rank @@
+Normal rank
@@ Property / cites work @@
+A note on bounded automorphisms of infinite graphs
+Normal rank
@@ Property / cites work @@
+Graphs with polynomial growth are covering graphs
@@ Property / cites work: Graphs with polynomial growth are covering graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Q4011119
@@ Property / cites work: Q4011119 / rank @@
+Normal rank
@@ Property / cites work @@
+On problems related to growth, entropy, and spectrum in group theory
+Normal rank
@@ Property / cites work @@
+On tree width, bramble size, and expansion
@@ Property / cites work: On tree width, bramble size, and expansion / rank @@
+Normal rank
@@ Property / cites work @@
+Groups of polynomial growth and expanding maps. Appendix by Jacques Tits
+Normal rank
@@ Property / cites work @@
+Q3772406
@@ Property / cites work: Q3772406 / rank @@
+Normal rank
@@ Property / cites work @@
+Parameters Tied to Treewidth
@@ Property / cites work: Parameters Tied to Treewidth / rank @@
+Normal rank
@@ Property / cites work @@
+A bound for groups of linear growth
@@ Property / cites work: A bound for groups of linear growth / rank @@
+Normal rank
@@ Property / cites work @@
+A note on the growth of transitive graphs
@@ Property / cites work: A note on the growth of transitive graphs / rank @@
+Normal rank
@@ Property / cites work @@
+A survey on graphs with polynomial growth
@@ Property / cites work: A survey on graphs with polynomial growth / rank @@
+Normal rank
@@ Property / cites work @@
+Linear min-max relation between the treewidth of an \(H\)-minor-free graph and its largest grid minor
+Normal rank
@@ Property / cites work @@
+The intrinsic dimensionality of graphs
@@ Property / cites work: The intrinsic dimensionality of graphs / rank @@
+Normal rank
@@ Property / cites work @@
+Logical aspects of Cayley-graphs: the group case
@@ Property / cites work: Logical aspects of Cayley-graphs: the group case / rank @@
+Normal rank
@@ Property / cites work @@
+Constant-degree graph expansions that preserve treewidth
+Normal rank
@@ Property / cites work @@
+Growth of finitely generated solvable groups
@@ Property / cites work: Growth of finitely generated solvable groups / rank @@
+Normal rank
@@ Property / cites work @@
+Q4407447
@@ Property / cites work: Q4407447 / rank @@
+Normal rank
@@ Property / cites work @@
+Graph minors. II. Algorithmic aspects of tree-width
+Normal rank
@@ Property / cites work @@
+Graph minors. V. Excluding a planar graph
@@ Property / cites work: Graph minors. V. Excluding a planar graph / rank @@
+Normal rank
@@ Property / cites work @@
+Quickly excluding a planar graph
@@ Property / cites work: Quickly excluding a planar graph / rank @@
+Normal rank
@@ Property / cites work @@
+Q3150763
@@ Property / cites work: Q3150763 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3491608
@@ Property / cites work: Q3491608 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3340884
@@ Property / cites work: Q3340884 / rank @@
+Normal rank
@@ Property / cites work @@
+Growth of finitely generated solvable groups and curvature of Riemannian manifolds
+Normal rank
@@ Property / cites work @@
+On tree-partition-width
@@ Property / cites work: On tree-partition-width / rank @@
+Normal rank
@@ Property / cites work @@
+Embedding planar graphs in four pages
@@ Property / cites work: Embedding planar graphs in four pages / rank @@
+Normal rank
@@ Property / cites work @@
+Planar graphs that need four pages
@@ Property / cites work: Planar graphs that need four pages / rank @@
+Normal rank