Fold-up baskets and 3-connected planar quadrangulations

Physical surfaces like paper are more restricted in folding than mathematical surfaces because physical surfaces cannot pass through one another or coincide. Perhaps there are maps on the sphere where no physical (a.k.a., self-avoiding) folding of the corresponding fold-up basket is possible? In limited experiments, it seems more common that no un-folding is possible. An example is the skeletal map of a hexagonal prism. This map is bipartite and polyhedral (planar and 3-vertex connected) so it should have an unfolded configuration containing positive volume; however, when assembled from 45-90-45 triangles in a flat configuration, it is seemingly impossible to fully unfold the surface because the two 6-sided faces (each with 6 right angles around the face center) are too hyperbolic to be happy in the unfolded configuration.

Similarly, maps that are only 2-connected (maps derived by inserting white vertices in edges can be no more than 2-connected) will have at least some portions that contain zero volume--even when fully un-folded--unless triangular faces are deformed to non-planarity (example below).

These observations draw attention to the 3-connected planar quadrangulations (3CPQ's,) which are maps that are polyhedral and quad-faced, as the best candidates for fold-up baskets. Voxel surfaces without topological holes (top image) are a familiar example of this class.

Some basic properties of quadrangulations and 3CPQ's in particular:

Planar quadrangulations are necessarily bipartite.

A simple (i.e., no loops or parallel edges) planar quadrangulation has connectivity either 2 or 3. Note in this regard that the path of three vertices (below) is not considered a simple planar quadrangulation.

3-connected quadrangulations are necessarily simple.

Given 1 of its 2 possible bicolorings, a planar quadrangulation is the radial of the underlying, pre-radial map revealed by drawing the black-vertex to black-vertex diagonal in each quad, and then erasing the original edges. The pre-radial will always be planar; but might not be 3-connected, simple, or bipartite. The pair of pre-radials derived from alternate bicolorings of the same quadrangulation are dual maps. If there is a face in the pre-radial whose boundary walk is not a cycle, then the radial has multiple edges.

A 3CPQ has at least 8 vertices of degree 3.

The smallest 3CPQ is the cube (8 vertices.)

There is no 3CPQ with 9 vertices. The only 3CPQ with 10 vertices has sparse6 code, “:I`ACPpaIOyFJSxn”. (Sparse6 codes can be viewed at the Sage Cell Server.) This object is known as the pseudo-double wheel of 8 faces, or W₈. Notice that the cube can be seen as W₆, and it is the smallest pseudo-double wheel that is 3-connected.

Sparse6 codes for 3CPQ's can be generated at The Combinatorial Object Server which uses Brinkmann and McKay's plantri software.

There is just one 3CPQ with 11 vertices: ":J`ACPpaIOxsOUiBe".

Among the three 3CPQ's with 12 vertices is ":K`ACGcaMGhBeQiRUO^", a.k.a., the double cube.

The number of 3-connected planar quadrangulations with n faces forms integer sequence A007022 in the Online Encyclopedia of Integer Sequences. The maps dual to 3CPQ's are simple, 4-regular, 3-connected planar maps: the same integer sequence counts those with n vertices.