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.

Geoweaving: Fold-Up Baskets from Dessins d'Enfants

I just gave a talk on this topic at Bridges Aalto 2022. Dessins d'enfants (children's drawings) are famous in number theory (be sure to catch Gareth Jones' short talk on that topic.) For our purposes, a dessin is a drawing on a closed surface such as the sphere (the only surface we will consider) drawn according to certain rules.

On the sphere, the prime rule is that the drawing must be connected, in other words, an ant scared to walk on the unmarked surface would still be able to walk from any part of the drawing to any other. That sort of drawing can be done by not lifting the pencil while drawing, or by drawing in any old way and going back later to add "bridges" for Mr. Ant.

Once you have a connected drawing:

1. Add black dots where lines end or cross.

2. Add white dots in the middle of the edges.

Now you have a proper dessin. There are a lot of dessins, and a more general way to make them. The next to last column in this table counts all dessins on the sphere having the same number of black-to-white edges.

The usefulness of dessins, for our purposes, is that they describe all the arrangements by which the Adams World Tile can seamlessly cover a closed surface (for us, the sphere.) What is the Adams World Tile? Oscar Sherman Adams invented it in 1929, calling his map projection "World in a Square II."

The beauty of the Adams World Tile is that multiple tiles can be tiled together to model a seamless periodic Earth.

Put a black dot at the South corner of the Adams World Tile, and a white dot at the North corner, and the dessin makes the arrangement of tiles explicit.

Maker details can be found in my slides for the Bridges talk and my paper in the Bridges Archive.

Math, Symmetry, and Weaving: the 3 dual pairs of hypermap representations

As described in a previous post, the classical hypermap representations come in three dual-pairs. Using the nomenclature of that earlier post, the dual-pairs are: Belyi-James, Walsh-Chess, and Cori-Quad. I am going to refer to these pairs of hypermap representations as: Symmetry, Math, and Weaving. Here is why.

The 'Symmetry' pair: Belyi and James

Because they expose the full symmetry of hypermaps--hypervertices, hyperfaces, and hyperedges are interchangeable roles--these two representations are undoubtedly the most fundamental, but perhaps the least useful. In the Belyi (a.k.a., the canonical triangulation) and the James representations the six Lins trialities are just the permutations of three colors. That is too much symmetry be saying anything useful about something with less symmetry.

The 'Math' dual-pair: Walsh and Chess

Math is a monochromatic world. Color and color names are avoided if possible. These two hypermap representations, Walsh and Chess, get by with just two colors (black and white) by associating specific graph elements (faces, vertices, respectively) exclusively with the third color--which therefore never needs naming. Walsh and Chess are in fact the most common hypermap representations in the math literature. See Bernardi and Fusy for a use of Chess.

The 'Weaving' dual-pair: Cori and Quad

These two hypermap representations, Cori and Quad, are 4-regular (respectively, on vertices, and on faces) and are readable as weaving diagrams.

Visualizing dessins as flow fields

A dessin with a source/sink flow sketched in.

The underlying dessin.

Maybe the easiest way to visualize how a dessin (a bicolored graph embedded in a surface) classifies Riemann surfaces is to sketch a flow field where, say, the black vertices are sources and the white vertices are sinks. Notice in the sketch above that the flow lines only reach nearest neighbors bordering a given face. Seeing the sketched flow lines as lines of longitude on the Earth (say from North to South) or as lines of constant phase angle on the Riemann sphere (from 0 to infinity) suggests a particular way in which multiple instances of the Riemann sphere can cover the surface.

The 6 representations of hypermaps

Hypergraphs are generalizations of graphs where a (hyper)edge is now a multiset (of any cardinality) of vertices. By contrast, in a simple graph an edge is a unique, cardinality-2 set of vertices. In a multigraph (parallel edges being allowed) uniqueness is no longer required. In a general graph (self-loops being allowed) an edge is a cardinality-2 multiset of vertices. By allowing the multiset of a hyperedge to have any cardinality, hypergraphs make a vast generalization of ordinary graphs: a hyperedge can connect any number of vertices, each with any degree of multiplicity. For example, there are only two graphs on one edge, but an infinity of hypergraphs on one hyperedge.

Surprisingly, when hypergraphs are embedded in surfaces they are easy to draw. For example, in the Walsh representation of hypermaps, they are simply bipartite, ordinary maps, embedded and drawn the same old way, but endowed with a proper 2-coloring of the vertices: the vertices have been colored black or white such that no edge connects two vertices of the same color. On many ordinary maps such a bicoloring is not possible; a map is said to be bipartite if such a bicoloring is possible.

Given an ordinary map, we can make it bipartite, and, in fact, bicolored, by inserting a white vertex in the middle of each edge. (In doing so, we have doubled the number of edges in the graph, and moved deeper into the combinatorial explosion of maps--the illusion that hypermaps are a subset of ordinary maps is just that.) This way of drawing a hypergraph lets us stay in the vocabulary of ordinary graphs if we wish. We just need to keep in mind that the white vertices represent generalized edges, octopi that can connect to any number of vertices with any multiplicity. For example, above is a hypermap expressing the idea that a particular friendship involves Peter, Paul, and Mary... and Peter twice.

In addition to the Walsh representation, there are five more classical representations of hypermaps. Only Walsh, Cori, and James are named for their first proponents, T.R.S. Walsh, Robert Cori, and Lynne D. James. For brevity, I have taken the liberty to call the "canonical triangulation" that arises in the study of Belyi functions,'Belyi'; and the checkerboard coloring lately championed by Bernardi and Fusy, 'Chess'; and what may be termed the 'canonical quadrangulation'--the canonical triangulation less the edges of the underlying bipartite graph, 'Quad'.

The chart above is explained in this earlier post.

Taking Walsh, which is the most intuitive and easiest to talk about with old vocabulary, as the ancestor, the other five are easily described as descendants by map operations. In fact, besides Dual, the only two map operations needed are Medial ('Ambo' in Conway polyhedron notation) and Kis (central triangulation of faces, also called stellation, or omnicapping.) Note: it is an error to use the same color (white) for faces and vertices in the Walsh representation. Once that is corrected (Walsh faces here are pink) all the other representations can receive their coloring by descent. That is, for example, if a face ultimately derives by map operations from a black vertex in Walsh, it is colored black. Both Cori and its dual, Quad, can be seen as diagrammatic of basket weaving, the one, as sparse weaving, the other as dense weaving. In those interpretations, the colors black and white code the same helical handedness.

Walsh representation

Belyi representation = Kis(Walsh)

Cori representation = Medial(Walsh)

Chess representation = Dual(Walsh)

James representation = Dual(Belyi)

Quad representation = Dual(Cori)