<p>It is <span class="math-container">$\Theta(n^2)$</span>. The argument to prove the lower bound is that we can send an all-pairs concurrent flow of value <span class="math-container">$1$</span> and congestion <span class="math-container">$O(n^4)$</span>, i.e., we can simultaneously send one unit of flow between every pair of vertices so that at most <span class="math-container">$O(n^4)$</span> units of flow go through any single vertex. This implies treewidth at least <span class="math-container">$\Omega(n^2)$</span>, because on treewidth-<span class="math-container">$k$</span> graphs with <span class="math-container">$|V|$</span> vertices any such flow must have congestion at least <span class="math-container">$\Omega(|V|^2/k)$</span>.</p>
<p>The construction to send the flow is as follows: Consider a pair of vertices represented by coordinates <span class="math-container">$(x_1,y_1,z_1)$</span> and <span class="math-container">$(x_2,y_2,z_2)$</span>. We send one flow path of value one that goes with straight lines <span class="math-container">$(x_1,y_1,z_1)$</span>-&gt;<span class="math-container">$(x_2,y_1,z_1)$</span>-&gt;<span class="math-container">$(x_2,y_2,z_1)$</span>-&gt;<span class="math-container">$(x_2,y_2,z_2)$</span>.</p>
<p>Now, given a vertex <span class="math-container">$(x,y,z)$</span>, for how many pairs <span class="math-container">$(x_1,y_1,z_1)$</span>, <span class="math-container">$(x_2,y_2,z_2)$</span> does their flow path go through <span class="math-container">$(x,y,z)$</span>? We observe that for a flow path between <span class="math-container">$(x_1,y_1,z_1)$</span> and <span class="math-container">$(x_2,y_2,z_2)$</span> to go through <span class="math-container">$(x,y,z)$</span>, at least two coordinates of <span class="math-container">$(x,y,z)$</span> must be equal to a corresponding coordinate in either <span class="math-container">$(x_1,y_1,z_1)$</span> or <span class="math-container">$(x_2,y_2,z_2)$</span>. Therefore, when given <span class="math-container">$(x,y,z)$</span>, we have four degrees of freedom when selecting the pair <span class="math-container">$(x_1,y_1,z_1)$</span>, <span class="math-container">$(x_2,y_2,z_2)$</span>, so the number of such pairs is <span class="math-container">$O(n^4)$</span>.</p>

CC BY-SA 4.0
2023-07-06T15:02:32.763Z
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.
Chandra Chekuri
CC BY-SA 4.0
2023-07-07T09:20:15.417Z
This is a new concept for me,  could you please offer some tutorials? I was even more confused after a Google search.
Jxb
CC BY-SA 4.0
2023-07-07T15:09:04.260Z
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. https://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. https://www.cambridge.org/core/books/abs/surveys-in-combinatorics-1997/tree-width-and-tangles-a-new-connectivity-measure-and-some-applications/50B61BC367CC21EA85F02038F3CC632D
Chandra Chekuri
CC BY-SA 4.0
2023-07-10T06:28:09.547Z
@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
CC BY-SA 4.0
2023-07-06T05:36:52.970Z
2023-07-06T05:36:52.970Z
Laakeri
<p>Here, by 3D-grid of sidelength <span class="math-container">$n$</span> I mean the graph <span class="math-container">$G=(V,E)$</span> with <span class="math-container">$V= \{1,\ldots,n\}^3$</span> and <span class="math-container">$E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$</span>.</p>
<p>I known how to get the treewidth of <span class="math-container">$n*n$</span> grid is exactly <span class="math-container">$n$</span> from bramble:</p>
<ol>
<li>Firstly, we can construct a tree decomposition of <span class="math-container">$width=n$</span>, which means <span class="math-container">$tw(n*n)\leq n$</span></li>
<li>Secondly, we can construct a bramble of order n, which means <span class="math-container">$tw(n*n)\geq n-1$</span></li>
</ol>
<blockquote>
<p><a href="https://www.sciencedirect.com/science/article/pii/S0095895683710270?via%3Dihub" rel="nofollow noreferrer">a graph has a bramble of order <span class="math-container">$k$</span> if and only if it has treewidth at least <span class="math-container">$k − 1$</span></a></p>
</blockquote>
<p>However, for a <span class="math-container">$n*n*n$</span> grid. We can simply get a path decomposition with pathwidth=<span class="math-container">$\Theta(n^2)$</span>. But I don't know how to construct a bramble of order <span class="math-container">$n^2$</span> to confirm its lower bound.</p>
<p><strong>My question:</strong> What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?</p>

CC BY-SA 4.0
2023-07-04T17:44:57.100Z
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.
Chandra Chekuri
CC BY-SA 4.0
2023-07-05T03:26:26.567Z
@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
CC BY-SA 4.0
2023-07-05T03:39:37.877Z
@ChandraChekuri Do you know bramble argument for $n*n*n$ grid?
Jxb
CC BY-SA 4.0
2023-07-05T14:49:05.223Z
Related question (notice that treewidth <= pathwidth): https://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k
Hermann Gruber
CC BY-SA 4.0
2023-07-06T01:31:43.543Z
@HermannGruber. I have gone through this answer and it can only provide an upper bound of treewidth if I understand correctly.
Jxb
CC BY-SA 4.0
2023-07-06T05:35:36.647Z
@Jxb yes, that answer provides only an upper bound.
Hermann Gruber
<graph-theory><treewidth>
What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?
Jxb
# What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

(Asked by: username_0 on 2023-07-04)

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$](https://www.sciencedirect.com/science/article/pii/S0095895683710270?via%3Dihub)

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?

**Tags:** graph-theory, treewidth
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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?  
> **username_0**: @ChandraChekuri Do you know bramble argument for $n*n*n$ grid?  
> **username_2**: Related question (notice that treewidth <= pathwidth): https://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k  
> **username_0**: @HermannGruber. I have gone through this answer and it can only provide an upper bound of treewidth if I understand correctly.  
> **username_2**: @Jxb yes, that answer provides only an upper bound.  

---

## 1 answers

### Answer by username_3 on 2023-07-06. Score: 3 | Accepted answer

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)$.

> **Comments:**
> **username_1**: 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.  
> **username_0**: This is a new concept for me,  could you please offer some tutorials? I was even more confused after a Google search.  
> **username_1**: 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. https://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. https://www.cambridge.org/core/books/abs/surveys-in-combinatorics-1997/tree-width-and-tangles-a-new-connectivity-measure-and-some-applications/50B61BC367CC21EA85F02038F3CC632D  
> **username_0**: @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.  

---

