5
$\begingroup$

This question is now also on https://cstheory.stackexchange.com/questions/4081/what-is-the-pathwidth-of-the-3d-grid-mesh-or-lattice-with-sidelength-k, where a discussion started, and one reference seems to be found.

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 smaller than $k^2$. 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$
2
  • 1
    $\begingroup$ It may help to look at a proof that the tree width of the $k \times k$ grid graph is $k$, and try to generalize that to $k \times k \times k$. Here are notes on the proof by Robin Thomas: people.math.gatech.edu/~thomas/TEACH/8863in05/notes0228.pdf $\endgroup$
    – Joseph O'Rourke
    Commented Dec 22, 2010 at 0:18
  • $\begingroup$ There seem to be a number of different proofs out there for the two dimensional case. The proof using the robber-cops game and observing that $k-1$ cops always leave one column and one row unattended seems to not generalize to 3D: There two such things need not intersect, and $12k$ cops suffice to limit the union of one row, one column, and one something. My proof idea goes rather in the direction of stating that too few cops will always leave a connected component of more than half the vertices. I think this goes in the direction of tangles, but I still have to read up a bit more on this. $\endgroup$
    – Riko Jacob
    Commented Dec 22, 2010 at 0:34

1 Answer 1

Reset to default
1
$\begingroup$

The question about pathwidth was fully answered at CSTheory, where it was also noted that the treewidth was not known at the time (as of 6 Jan 2011).

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .