# What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

Here, by 3D-grid of sidelength $$n$$ I mean the graph $$G=(V,E)$$ with $$V= \{1,\ldots,n\}^3$$ and $$E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$$.

I known how to get the treewidth of $$n*n$$ grid is exactly $$n$$ from bramble:

1. Firstly, we can construct a tree decomposition of $$width=n$$, which means $$tw(n*n)\leq n$$
2. Secondly, we can construct a bramble of order n, which means $$tw(n*n)\geq n-1$$

a graph has a bramble of order $$k$$ if and only if it has treewidth at least $$k − 1$$

However, for a $$n*n*n$$ grid. We can simply get a path decomposition with pathwidth=$$\Theta(n^2)$$. But I don't know how to construct a bramble of order $$n^2$$ to confirm its lower bound.

My question: What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

• It is $\Omega(n^2)$ from a well-linked set argument but if you want a tight bound in terms of constants I do not know the right/clean answer. Commented Jul 4, 2023 at 17:44
• @ChandraChekuri $\Omega(n^2)$ is enough, I believe well-linked argument is right. However, I can't exactly write the proof about the size of $n^2$-linked set, how to describe there are enough paths?
– Jxb
Commented Jul 5, 2023 at 3:26
• @ChandraChekuri Do you know bramble argument for $n*n*n$ grid?
– Jxb
Commented Jul 5, 2023 at 3:39
• Related question (notice that treewidth <= pathwidth): cstheory.stackexchange.com/questions/4081/… Commented Jul 5, 2023 at 14:49
• @HermannGruber. I have gone through this answer and it can only provide an upper bound of treewidth if I understand correctly.
– Jxb
Commented Jul 6, 2023 at 1:31

It is $$\Theta(n^2)$$. The argument to prove the lower bound is that we can send an all-pairs concurrent flow of value $$1$$ and congestion $$O(n^4)$$, i.e., we can simultaneously send one unit of flow between every pair of vertices so that at most $$O(n^4)$$ units of flow go through any single vertex. This implies treewidth at least $$\Omega(n^2)$$, because on treewidth-$$k$$ graphs with $$|V|$$ vertices any such flow must have congestion at least $$\Omega(|V|^2/k)$$.

The construction to send the flow is as follows: Consider a pair of vertices represented by coordinates $$(x_1,y_1,z_1)$$ and $$(x_2,y_2,z_2)$$. We send one flow path of value one that goes with straight lines $$(x_1,y_1,z_1)$$->$$(x_2,y_1,z_1)$$->$$(x_2,y_2,z_1)$$->$$(x_2,y_2,z_2)$$.

Now, given a vertex $$(x,y,z)$$, for how many pairs $$(x_1,y_1,z_1)$$, $$(x_2,y_2,z_2)$$ does their flow path go through $$(x,y,z)$$? We observe that for a flow path between $$(x_1,y_1,z_1)$$ and $$(x_2,y_2,z_2)$$ to go through $$(x,y,z)$$, at least two coordinates of $$(x,y,z)$$ must be equal to a corresponding coordinate in either $$(x_1,y_1,z_1)$$ or $$(x_2,y_2,z_2)$$. Therefore, when given $$(x,y,z)$$, we have four degrees of freedom when selecting the pair $$(x_1,y_1,z_1)$$, $$(x_2,y_2,z_2)$$, so the number of such pairs is $$O(n^4)$$.

• One can use similar routing to show that the $n^2$ vertices of the side of the grid is $c$-well-linked set for some fixed constant $c < 1$. A set $X$ is a $c$-well-linked set if for any partition of $X$ into $A$ and $B$ there are $\min(|A|,|B|)$ disjoint paths between $A$ and $B$ with congestion at most $c$. It is known that treewidth and size of well-linked sets are within a small constant of each other. Commented Jul 6, 2023 at 15:02
• This is a new concept for me, could you please offer some tutorials? I was even more confused after a Google search.
– Jxb
Commented Jul 7, 2023 at 9:20
• Unfortunately there isn't a clean survey to point to. You can read a bit about these connections in a paper of mine with Julia Chuzhoy. arxiv.org/pdf/1305.6577.pdf (see Section 2 which describes well-linked sets and connection to treewidth). I also like Bruce Reed's survey on treewidth and tangles. cambridge.org/core/books/abs/surveys-in-combinatorics-1997/… Commented Jul 7, 2023 at 15:09
• @ChandraChekuri. Yeah, I can learn the connection between treewidth and well-linked sets from your paper. But I don't understand the connection of "congestion" and treewidth from Laakeri's answer.
– Jxb
Commented Jul 10, 2023 at 6:28