U.C. Berkeley Math.
Hexahedron here means combinatorially equivalent to a cube.
This can be taken as a question in combinatorial topology, where the faces can be curvilinear, or one can insist that the hexahedra really have linear faces. Let's look at the topological question first. One way to view this problem is to dualize, that is, take the dual subdivision. The dual of a cell division of the sphere by quadrilaterals is characterized by the property that edges meet in 4's. You can think of it as a subdivision of the sphere obtained by drawing some possibly self-intersecting closed curves that meet themselves and meet each other transversely.