13
$\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.

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

2 Answers 2

Reset to default
14
$\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.
Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for kindly sharing your new result (and paper!) Also, welcome to TCS SE :) $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Jan 6, 2011 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
    Commented Jan 6, 2011 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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Note that the paper is written in Japanese. $\endgroup$
    – Tsuyoshi Ito
    Commented Jan 5, 2011 at 4:48
  • 1
    $\begingroup$ @Tsuyoshi: Yes, we may need your help :) $\endgroup$
    – Hsien-Chih Chang 張顯之
    Commented Jan 5, 2011 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
    Commented Jan 5, 2011 at 6:12
  • 1
    $\begingroup$ A paper "bandwidth and pathwidth of three-dimensional grids" by Suda and Otachi (but not Yamazaki) is now up at arXiv: arxiv.org/abs/1101.0964 $\endgroup$
    – David Eppstein
    Commented Jan 6, 2011 at 1:52
  • 1
    $\begingroup$ @David: Thanks for the link. Koichi declined to be a coauthor, since in his opinion, his contribution is not enough. $\endgroup$
    – Yota Otachi
    Commented Jan 6, 2011 at 4:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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