What is the pathwidth of the 3D-grid (mesh or lattice) with sidelength k? I asked this question some weeks ago at mathoverflow, 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.
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 of our paper to arXiv.


B. Bollobás and I. Leader, Compressions and isoperimetric inequalities, J. Combin. Theory Ser. A 56 (1991) 47-62.
C.H. FitzGerald, Optimal indexing of the vertices of graphs, Math. Comp. 28 (1974), 825-831.
L.H. Harper, Optimal numberings and isoperimetric problems on graphs, J. Combin. Theory 1 (1966) 385-393.
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).
H.S. Moghadam, Bandwidth of the product of $n$ paths, Congr. Numer. 173 (2005) 3-15.