<p>The pathwidth of 3D-grids has been studied by Ryohei Suda, Yota Otachi and Koichi Yamazaki in the paper <a href="http://ci.nii.ac.jp/naid/110007227312" rel="noreferrer">Pathwidth of 3-dimensional grids</a>, IEICE Tech. Report, 2009.</p>

<p>It is claimed in the abstract of the paper that</p>

<blockquote>
  <p>In this paper, we give the pathwidth of 3-dimentional grids in closed form, by determining their vertex boundary width.</p>
</blockquote>

<p>However the precise bound is not stated in the abstract, and currently I cannot access the full paper. Maybe you can contact the authors privately, and post an answer to this question by yourself, if the authors are willing to share the result.</p>

CC BY-SA 2.5
2011-01-05T04:48:43.900Z
Note that the paper is written in Japanese.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-05T04:52:46.813Z
@Tsuyoshi: Yes, we may need your help :)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-05T06:12:41.767Z
I have a physical access to the manuscript (and can understand Japanese).  According to the authors, the pathwidth of $P_{\ell}\times P_{m}\times P_{n}$ is $\ell m$ if $\ell + m \leq n + 2$ and $\ell m - \lceil (\frac{\ell+m-n-1}{2})^2 \rceil$ otherwise, where $P_k$ is a path with $k$ vertices, and $\ell \leq m \leq n$.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-05T07:28:48.660Z
@Yoshio: This deserves to be an answer, since it implies $\mathsf{pw}(P^3_k) = \frac{3}{4}k^2 + O(k)$, which answers the question.
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-05T08:13:17.223Z
Thanks. Looks like I don't have to feel bad for not finding that reference myself. I am curious for the details.
Riko Jacob
CC BY-SA 2.5
2011-01-06T01:52:40.527Z
A paper "bandwidth and pathwidth of three-dimensional grids" by Suda and Otachi (but not Yamazaki) is now up at arXiv: http://arxiv.org/abs/1101.0964
David Eppstein
CC BY-SA 2.5
2011-01-06T04:21:06.277Z
@David: Thanks for the link. Koichi declined to be a coauthor, since in his opinion, his contribution is not enough.
Yota Otachi
CC BY-SA 2.5
2011-01-05T03:41:39.880Z
2011-01-05T03:41:39.880Z
Hsien-Chih Chang 張顯之
<p>The pathwidth of $P^3_k$ can be determined as a corollary to some known results.
FitzGerald [2] showed that the bandwidth of $P^3_k$ is $\lfloor \frac{3}{4} k^{2} + \frac{1}{2} k \rfloor$.
Harper [3] showed a condition such that if a graph satisfies the condition, then its pathwidth and bandwidth are the same.
Moghadam [4,5] and Bollobás and Leader [1] independently showed that any multi-dimensional grid satisfies Harper's condition.
These results imply that the pathwidth of $P^3_k$ is also $\lfloor \frac{3}{4} k^{2} + \frac{1}{2}k \rfloor$.</p>

<p>In our paper mentioned by Hsien-Chih, we generalized FitzGerald's result as Yoshio explained.
I believe the treewidth of $P^3_k$ is not known.</p>

<p>FYI: I've just submitted an <a href="http://arxiv.org/abs/1101.0964">English version</a> of our paper to arXiv.</p>

<ol>
<li>B. Bollobás and I. Leader, Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A 56 (1991) 47-62.</li>
<li>C.H. FitzGerald, Optimal indexing of the vertices of graphs, Math. Comp. 28 (1974), 825-831.</li>
<li>L.H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory 1 (1966) 385-393.</li>
<li>H.S. Moghadam, Compression operators and a solution to the bandwidth problem of the product of $n$ paths, Ph.D. thesis, University of California, Riverside (1983).</li>
<li>H.S. Moghadam, Bandwidth of the product of $n$ paths, Congr. Numer. 173 (2005) 3-15.</li>
</ol>

CC BY-SA 2.5
2011-01-06T01:33:19.953Z
Thank you for kindly sharing your new result (and paper!) Also, welcome to TCS SE :)
Hsien-Chih Chang 張顯之
CC BY-SA 2.5
2011-01-06T04:30:03.540Z
@Hsien-Chih: You made me decide to share our result :-) Thanks. In fact, I'm also new for arXiv.
Yota Otachi
CC BY-SA 2.5
2011-01-06T01:25:54.587Z
2011-01-06T01:25:54.587Z
Yota Otachi
<p>I asked this question some weeks ago at <a href="https://mathoverflow.net/questions/50103/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k">mathoverflow</a>, but I got no reply.</p>

<p>Here, by 3D-grid of sidelength $k$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,k\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$, i.e., the nodes are placed at 3-dimensional integer coordinates between 1 and $k$, and a node is connected to the at most 6 other nodes that differ in precisely one coordinate by one.</p>

<p>What is the name of this graph? I'll use 3D grid, but perhaps 3D mesh or 3D lattice are what other people are used to.</p>

<blockquote>
  <p>What is the treewidth or pathwidth of
  this graph?  Is this already published
  somewhere?</p>
</blockquote>

<p>I know already that $tw(G) = (3/4) k^2 + O(k)$, i.e. it is really smaller than $k^2$.
To me, this suggests that the standard arguments showing that the $k\times k$ 2D-grid has treewidth and pathwidth $k$ will not easily generalize.</p>

<p>To see this, we consider a path decomposition that "sweeps" the grid using mainly node-sets of the form $S_c= \{(x,y,z)\mid x+y+z = c\}$. 
Observe $|S_c| \leq (3/4) k^2 + O(k)$, $S_{3/2 k}$ being the largest such set.
The sets between $S_c$ and $S_{c+1}$ are created by sweeping with a line and need $O(k)$ additional nodes to be separators. More precisely, use the sets 
$S_{c,d} = \{(x,y,z)\mid (x+y+z = c \wedge x \leq d ) \vee (x+y+z = c \wedge x \geq d ) \}$ as a path decomposition of $G$.</p>

<p>I also have an idea for a proof that shows $tw(G) = \Omega(k^2)$, but that is not finished yet.</p>

CC BY-SA 2.5
2011-01-04T13:21:13.667Z
$|S_c| = \Omega(k^2)$ for $c=\lfloor k/2 \rfloor$. Am I missing something?
Sariel Har-Peled
CC BY-SA 2.5
2011-01-04T13:32:05.500Z
Sure. But $S_c$ is only used in the upper bound.  What I really care about is a lower bound.
Riko Jacob
CC BY-SA 2.5
2011-01-04T17:57:04.193Z
You may be interested in this paper: http://www.springerlink.com/content/3nmjlc1g5emx9vpk/. If you can calculate the "queue number" of your graph, then you'll be given a lower bound on its path-width using Theorem 1 which states that $\mathsf{qn}(G) \leq \mathsf{pw}(G)$ for any graph $G$.
Mathieu Chapelle
CC BY-SA 2.5
2011-01-04T23:22:55.940Z
Oh. I see. You meant $(3/4)k^2$.
Sariel Har-Peled
CC BY-SA 2.5
2011-01-05T00:27:49.347Z
@Sariel: I edited the question to avoid the same confusion.
Tsuyoshi Ito
CC BY-SA 2.5
2011-01-05T09:14:35.307Z
Sorry and thanks for editing.  I did not even realize that this might lead to confusion.
Riko Jacob
<reference-request><graph-theory><co.combinatorics><treewidth><integer-lattice>
What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?
Riko Jacob
# What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k?

(Asked by: username_0 on 2011-01-04)

I asked this question some weeks ago at [mathoverflow](https://mathoverflow.net/questions/50103/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k), but I got no reply.

Here, by 3D-grid of sidelength $k$ I mean the graph $G=(V,E)$ with $V= \{1,\ldots,k\}^3$ and $E=\{( (a,b,c) ,(x,y,z) ) \mid |a-x|+|b-y|+|c-z|=1 \}$, i.e., the nodes are placed at 3-dimensional integer coordinates between 1 and $k$, and a node is connected to the at most 6 other nodes that differ in precisely one coordinate by one.

What is the name of this graph? I'll use 3D grid, but perhaps 3D mesh or 3D lattice are what other people are used to.

> What is the treewidth or pathwidth of
> this graph? Is this already published
> somewhere?

I know already that $tw(G) = (3/4) k^2 + O(k)$, i.e. it is really smaller than $k^2$.
To me, this suggests that the standard arguments showing that the $k\times k$ 2D-grid has treewidth and pathwidth $k$ will not easily generalize.

To see this, we consider a path decomposition that "sweeps" the grid using mainly node-sets of the form $S\_c= \{(x,y,z)\mid x+y+z = c\}$.
Observe $|S\_c| \leq (3/4) k^2 + O(k)$, $S\_{3/2 k}$ being the largest such set.
The sets between $S\_c$ and $S\_{c+1}$ are created by sweeping with a line and need $O(k)$ additional nodes to be separators. More precisely, use the sets
$S\_{c,d} = \{(x,y,z)\mid (x+y+z = c \wedge x \leq d ) \vee (x+y+z = c \wedge x \geq d ) \}$ as a path decomposition of $G$.

I also have an idea for a proof that shows $tw(G) = \Omega(k^2)$, but that is not finished yet.

**Tags:** reference-request, graph-theory, co.combinatorics, treewidth, integer-lattice
> **Comments:**
> **username_1**: $|S_c| = \Omega(k^2)$ for $c=\lfloor k/2 \rfloor$. Am I missing something?  
> **username_0**: Sure. But $S_c$ is only used in the upper bound.  What I really care about is a lower bound.  
> **username_2**: You may be interested in this paper: http://www.springerlink.com/content/3nmjlc1g5emx9vpk/. If you can calculate the "queue number" of your graph, then you'll be given a lower bound on its path-width using Theorem 1 which states that $\mathsf{qn}(G) \leq \mathsf{pw}(G)$ for any graph $G$.  
> **username_1**: Oh. I see. You meant $(3/4)k^2$.  
> **username_3**: @Sariel: I edited the question to avoid the same confusion.  
> **username_0**: Sorry and thanks for editing.  I did not even realize that this might lead to confusion.  

---

## 2 answers

### Answer by username_7 on 2011-01-06. Score: 14 | Accepted answer

The pathwidth of $P^3\_k$ can be determined as a corollary to some known results.
FitzGerald [2] showed that the bandwidth of $P^3\_k$ is $\lfloor \frac{3}{4} k^{2} + \frac{1}{2} k \rfloor$.
Harper [3] showed a condition such that if a graph satisfies the condition, then its pathwidth and bandwidth are the same.
Moghadam [4,5] and Bollobás and Leader [1] independently showed that any multi-dimensional grid satisfies Harper's condition.
These results imply that the pathwidth of $P^3\_k$ is also $\lfloor \frac{3}{4} k^{2} + \frac{1}{2}k \rfloor$.

In our paper mentioned by Hsien-Chih, we generalized FitzGerald's result as Yoshio explained.
I believe the treewidth of $P^3\_k$ is not known.

FYI: I've just submitted an [English version](http://arxiv.org/abs/1101.0964) of our paper to arXiv.

1. B. Bollobás and I. Leader, Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A 56 (1991) 47-62.
2. C.H. FitzGerald, Optimal indexing of the vertices of graphs, Math. Comp. 28 (1974), 825-831.
3. L.H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory 1 (1966) 385-393.
4. H.S. Moghadam, Compression operators and a solution to the bandwidth problem of the product of $n$ paths, Ph.D. thesis, University of California, Riverside (1983).
5. H.S. Moghadam, Bandwidth of the product of $n$ paths, Congr. Numer. 173 (2005) 3-15.

> **Comments:**
> **username_4**: Thank you for kindly sharing your new result (and paper!) Also, welcome to TCS SE :)  
> **username_7**: @Hsien-Chih: You made me decide to share our result :-) Thanks. In fact, I'm also new for arXiv.  

---

### Answer by username_4 on 2011-01-05. Score: 6

The pathwidth of 3D-grids has been studied by Ryohei Suda, Yota Otachi and Koichi Yamazaki in the paper [Pathwidth of 3-dimensional grids](http://ci.nii.ac.jp/naid/110007227312), IEICE Tech. Report, 2009.

It is claimed in the abstract of the paper that

> In this paper, we give the pathwidth of 3-dimentional grids in closed form, by determining their vertex boundary width.

However the precise bound is not stated in the abstract, and currently I cannot access the full paper. Maybe you can contact the authors privately, and post an answer to this question by yourself, if the authors are willing to share the result.

> **Comments:**
> **username_3**: Note that the paper is written in Japanese.  
> **username_4**: @Tsuyoshi: Yes, we may need your help :)  
> **username_5**: I have a physical access to the manuscript (and can understand Japanese).  According to the authors, the pathwidth of $P_{\ell}\times P_{m}\times P_{n}$ is $\ell m$ if $\ell + m \leq n + 2$ and $\ell m - \lceil (\frac{\ell+m-n-1}{2})^2 \rceil$ otherwise, where $P_k$ is a path with $k$ vertices, and $\ell \leq m \leq n$.  
> **username_4**: @Yoshio: This deserves to be an answer, since it implies $\mathsf{pw}(P^3_k) = \frac{3}{4}k^2 + O(k)$, which answers the question.  
> **username_0**: Thanks. Looks like I don't have to feel bad for not finding that reference myself. I am curious for the details.  
> **username_6**: A paper "bandwidth and pathwidth of three-dimensional grids" by Suda and Otachi (but not Yamazaki) is now up at arXiv: http://arxiv.org/abs/1101.0964  
> **username_7**: @David: Thanks for the link. Koichi declined to be a coauthor, since in his opinion, his contribution is not enough.  

---

