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.