Which polycubes have planar graphs?
Joe Malkevitch recently asked me: which polycubes have planar graphs?
By a polycube, I mean a set of unit cubes in the three-dimensional integer lattice whose dual graph (with vertices for cubes and edges for cubes that share a square with each other) is connected; Malkevitch had a more restrictive definition in mind in which the boundary of the union of the cubes is a connected manifold, but that turns out not to make a difference for this problem. The graph of a polycube is formed by the vertices and edges of the cubes in this set.
The answer turns out to be: the polycubes that have a tree-like structure that can be formed by adding cubes one at a time, at each step adding a cube that touches the previous cubes in exactly one of its squares. One direction is easy: if you add cubes in this way, you end up changing the graph by replacing a quadrilateral face by five quadrilaterals, which preserves planarity.
In the other direction, suppose you have a polycube that cannot be constructed in this way, and build it up by adding cubes one at a time in a preorder traversal of a spanning tree of the dual graph. At some point, you will add a cube \( c \) that is adjacent not only to its parent \( p \) in the tree, but to some other part of the already-constructed polycube. If you contract the parts of \( c \) and \( p \) that are not on their shared square, and contract the path in the polycube connecting those parts, you can get a \( K_{3,3} \) graph minor out of the graph of the polycube, showing that it must be nonplanar.
The same question is also interesting when you ask about the graph of the boundary of the polycube, but it has a simpler answer: if the boundary is connected, then it is planar if and only if the polycube is a topological ball.
Comments:
2014-09-25T11:38:01Z
Could not resist commenting on this post.
A few years ago I tried to work out some properties of a class of such graphs. I called it pendulum graphs which were composed of gluing sides of cubes such that no cycles are formed by these cube arrangements. I allowed a line of cubes to extend to infinity, hence the name pendulum (infinite string and a finite bob). These are not only planar, but also bipartite, Hamiltonian (with finite string) and unit distance in the plane. Formal proofs turned out to be easy after Dr. Felsner suggested that they were cube duals of trees.
Since I was looking into the planarity issue, this idea can be generalized to other platonic solids (although other properties may vary). Not much deep stuff, but fun to think about.
Regards,
Uma kant