The smallest simple planar quadrangulations

The smallest simple planar (aka, spherical) quadrangulation has 3 vertices, so let's call it Q3. Q3 has one face (exemplifying the rule that all planar quadrangulations have 2 more vertices than faces.) Many authorities, the authors of the plantri program included, do not classify Q3 as a quadrangulation because the boundary of its face is not a cycle, but we include it here. There is also a unique simple planar quadrangulation for 4 vertices, and likewise for 5 vertices, so we will call them Q4 and Q5:

Now we come to a great divide in the realm of simple planar quadrangulations. There are two simple planar quadrangulations with 6 vertices, so we will have to distinguish them as Q6.1 and Q6.2:

But that is not the great divide. Q6.1 and Q6.2 are the smallest simple planar quadrangulations with a separating 4-cycle (aka, a non-facial 4-cycle.) A non-facial 4-cycle outlines a locus where we can imagine two separate quadrangulations have been glued face-to-face at a single quad face. Notice that if we glue two planar quadrangulations (SPQ's) together at more than one face, the result takes us outside the SPQ class: the compound is no longer a quadrangulation of a sphere, either by virtue of achieving a higher topology, or having at least one edge that is not embedded in the surface.

In this sense an SPQ with a non-facial 4-cycle is composite. For example, it is easy to see how both Q6.1 and Q6.2 could have been formed by gluing together two copies of Q5 together at a single face.

Of course the business of gluing quadrangulations together can be iterated, but all subsequent attachments must be arranged in a tree-like pattern. If we ever form a closed circuit of SPQ's, we will have made a torus rather than a sphere.

It is very handy that compositions of SPQ's are always tree-like. A tree graph always has at least two leaf-edges that are attached to the rest of the tree at only one point. So a composite SPQ always has at least two leaf components that are attached to the rest of the composition by a single non-facial 4-cycle. If we possess reduction rules that reduce such a component down to its one non-facial 4-cycle, we will discover that the 4-cycle in question is no longer non-facial, so we can move on to another of its (once again, at least two) leaf components. In this way, as Fuchs and Gellert point out, we never need to operate on a vertex that lies in a non-facial 4-cycle.

Degree-2 vertices are not so useful for enclosing volume, and are easily folded down when they occur; mainly we are only interested in degree-2 vertices when they are necessary stepping stones to growing a less baroque shape. Interest therefore turns to certain more restricted classes of simple planar quadrangulations. Several restricted classes can be generated in plantri and then copy-and-pasted as sparse6 codes to be rendered in 3d at SageMathCell.

The Online Encyclopedia of Integer Sequences has enumerations of these SPQ classes: A113201: simple planar quadrangulations; A078666: simple planar quadrangulations, minimum degree-3; A007022: simple planar quadrangulations, 3-connected; A002880: simple planar quadrangulations, 3-connected, without separating 4-cycles;

Per Nagashima et al., a simple quadrangulation (>Q5) with no separating 4-cycle is 3-connected; and if it is 3-connected it is also minimum degree-3, so A002880 more generally counts all simple planar quadrangulations with no separating 4-cycles having at least 6 vertices. The count is unaffected by adding "3-connected," or "minimum-degree-3" as constraints.