12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $|S_c| = \Omega(k^2)$ for $c=\lfloor k/2 \rfloor$. Am I missing something? $\endgroup$ – Sariel Har-Peled Jan 4 '11 at 13:21
  • $\begingroup$ Sure. But $S_c$ is only used in the upper bound. What I really care about is a lower bound. $\endgroup$ – Riko Jacob Jan 4 '11 at 13:32
  • $\begingroup$ You may be interested in this paper: 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$. $\endgroup$ – Mathieu Chapelle Jan 4 '11 at 17:57
  • $\begingroup$ Oh. I see. You meant $(3/4)k^2$. $\endgroup$ – Sariel Har-Peled Jan 4 '11 at 23:22
  • 1
    $\begingroup$ @Sariel: I edited the question to avoid the same confusion. $\endgroup$ – Tsuyoshi Ito Jan 5 '11 at 0:27
13
$\begingroup$

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.

  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.
$\endgroup$
  • $\begingroup$ Thank you for kindly sharing your new result (and paper!) Also, welcome to TCS SE :) $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 6 '11 at 1:33
  • $\begingroup$ @Hsien-Chih: You made me decide to share our result :-) Thanks. In fact, I'm also new for arXiv. $\endgroup$ – Yota Otachi Jan 6 '11 at 4:30
6
$\begingroup$

The pathwidth of 3D-grids has been studied by Ryohei Suda, Yota Otachi and Koichi Yamazaki in the paper Pathwidth of 3-dimensional grids, 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.

$\endgroup$
  • $\begingroup$ Note that the paper is written in Japanese. $\endgroup$ – Tsuyoshi Ito Jan 5 '11 at 4:48
  • $\begingroup$ @Tsuyoshi: Yes, we may need your help :) $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 5 '11 at 4:52
  • 4
    $\begingroup$ 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$. $\endgroup$ – Yoshio Okamoto Jan 5 '11 at 6:12
  • $\begingroup$ @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. $\endgroup$ – Hsien-Chih Chang 張顯之 Jan 5 '11 at 7:28
  • $\begingroup$ Thanks. Looks like I don't have to feel bad for not finding that reference myself. I am curious for the details. $\endgroup$ – Riko Jacob Jan 5 '11 at 8:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.