Kids make completely foldable objects

Scene at the "Make a Completely Foldable Object" booth.

Folks of all ages made completely foldable objects at the Silver Spring Mini Maker Faire on September 29, 2013. The example I demonstrated was an octahedron that folds down to a single stack of triangles. Participants as young as six years-old made their own. Two participants went further, creating their own freeform completely foldable objects, and succeeded in folding them down to a single stack of triangles.

An ambitious, freeform CFO...

and, a little later, all folded down to one stack.

A freeform completely foldable object.

After some puzzle solving, it's all folded down to a single stack.

Crumple

Me with Crumple at Nuit Blanche.

Crumple is an animated sculpture composed of 128 identical folded pieces of aluminum sheet metal. It is animated by inflation of an internal plastic bag. It was exhibited at Washington DC's popular Nuit Blanche on September 28-29, 2013. This album shows photos of Crumple under construction. This videos shows Crumple in action.

Maquette for a completely foldable sculpture

Maquette for Crumple, a kinetic sculpture proposed for DC's Nuit Blanche.

Crumple maquette in a different state of inflation.

Left and right patterns.

Cutting from aluminum flashing with strong scissors.

Assembling with Bassetti-style rubber band hinges (#19 bands doubled.)

Improved completely-foldable octahedron

Completely foldable octahedron with Bassetti hinges and box closures on the outside.

View of the rubber band hinges and the unfolded shape of the triangle units.

Triplets of Dyck words code the physical configurations completely folded surfaces

In phantom configurations of a completely folded surface, the triangles and hinges can intersect and coincide. In semi-physical configurations of a completely folded surface, triangles do not coincide (they have a physical, stacked order,) but hinges may cross through each other. In physical configurations of a completely folded surface, triangles do not coincide and hinges do not cross. Since a surface in a physical configuration has no self-intersection, such can never be a non-orientable surface without boundary.

A completely folded surface in either a physical or semi-physical configuration has a stack of triangles—and consequently three stacks of edges—hinged together in a particular way. We assume in the following that the surface has no boundary: therefore every triangle edge is connected to one other triangle edge in the same edge stack by a hinge.

If hinges are permitted to cross each other (the semi-physical condition), then the hinge connections in a given edge stack are a perfect matching of those edges.

If hinges are not permitted to cross (the physical condition), then our boundary-less surface must be orientable, and the hinge connections in a given edge stack are a non-crossing partition of those edges. A natural way to code a non-crossing partition is as a parenthesis word, or Dyck word. When written out as a Dyck word, it is easy to imagine the non-crossing arrangement of the hinges in the edge stack by simply connecting the paired parentheses with arcs above the Dyck word, e.g.:

( ) ( ) ( ( ) ).

Since there are three edge stacks, a triplet of Dyck words of the same length can encode a completely folded physical configuration.

The number of Dyck words of length 2n are counted by the nth Catalan number:

1, 1, 2, 5, 14, 42, 132, 429, 1430, ....

and triplets of Dyck words are counted by the cube of the nth Catalan number:

1, 1, 8, 125, 2744, 74088, 2299968, 78953589, 2924207000, ....

For triangle-faced maps that are, as usual, without boundary, but possibly composed of multiple disjoint components, the same daunting integer sequence counts their completely folded configurations when 2n is the number of triangles in the stack. In using the cube of Catalan numbers we are counting as different every possible difference in the completely folded configuration: e.g., simply rotating the stack, flipping it over, enantiomorph-ing the surface or the folded configuration, etc. More significantly, since the map is permitted to have multiple disjoint components, we also count every possible way the multiple components can be arranged in the stack, including the different ways they can enclose each other.

Though it is appealing to think that we can now dial up the phone number of any completely folded configuration that will ever be designed, the combinatorial explosion frustrates "cold-calling" as a technique to discover new designs. Nonetheless, dialing from even the shortest phonebook puts us in touch with shapes that we humans have largely avoided thinking about. A phonebook with n<=2 has 1 + 1 + 8 = 10 entries in it. The configurations that pick up the phone are the empty set; the triangular pillow; a stack of two triangular pillows; a triangular pillow enclosing another triangular pillow; two triangular "ears" that have seamed along a double edge and folded along the seam—in three rotations; and the same "double ear" with one ear tucked inside the other—also in three rotations. 

Origami vs. Complete Folding in 3D printing

ORIGAMI:
A large machine makes a creased sheet that folds to a small object.

COMPLETE FOLDING:
A small machine makes a folded stack that unfolds to a large object.

Regular {3, 2n} maps

Weddslist has a listing of regular maps.

A necessary condition for a regular map to be a CFTM is that its Schläfli formula be {3, 2n} for some positive integer n.

Regular maps meeting this condition include:

Orientable genus 0
di-triangle {3, 2} (it seems the only configuration is folded)
octahedron {3,4}

Orientable genus 1
{3, 6} (1, 1)  (only one vertex)
{3, 6} (0, 2)  6 triangles ()(()); ((())); (())() (it seems the only configuration is folded)
{3, 6} (2, 2)  8 triangles
{3, 6} (1, 3) 14 triangles
{3, 6} (3, 3) 18 triangles
{3, 6} (0, 4) 24 triangles
{3, 6} (2, 4) 26 triangles
{3, 6} (4, 4) 32 triangles
etc.

Orientable genus 2
S2:{3, 8} 16 triangles

Non-orientable genus 1
hemioctahedron {3, 4} 4 triangles

Non-orientable genus 6
C6: {3, 10} 10 20 triangles
C6: {3, 10} 5 20 triangles

Parity embedding: completely foldable triangulations from Tait colored maps

The tetrahedron has a Tait coloring, but its dual is not a CFTM. We fix this by half-twisting every edge that has the same color orientation at each end.

If a cubic map has a Tait coloring, then it is possible to find a new embedding for its edge-colored graph such that the dual—a triangular map—is node tricolorable, and thus a completely foldable triangular map (CFTM).

Represent the Tait-colored cubic map as a ribbon graph. Apply a half-twist to any edge that has the same color orientation around the nodes at each end. This edge-selective application of the skew operation yields the ribbon graph of a map having the same number of nodes and edges, but (probably) a different number of faces, and therefore a different Euler characteristic and a different surface topology.

In the new map we always see color orientation reversing at each successive node in a walk on the surface. Thus, if a walk closes after an odd number of steps, our sense of orientation must therefore have reversed. Similarly, if a walk closes after an even number of steps, our sense of orientation must therefore have been preserved. Such an embedding, where every even closed walk is orientation-preserving and every odd closed walk is orientation-reversing, is called a parity embedding. In this new, custom made embedding, the Tait-colored graph has a CFTM as its dual.

Since a walk around the boundary of a face can never be orientation reversing (a face is a topological disk,) every face in a parity embedding is even.

For example, the Tait coloring of the tetrahedron is unique (deleting edges of any one color leaves a 4-cycle.) The unique Tait coloring gives the same color orientation to all four nodes. We need therefore to apply the skew operation to all the edges. That gives us the Petrie dual of the tetrahedron: the hemicube, a map on the projective plane with three 4-sided faces. Its dual, the hemioctahedron, also in the projective plane is the completely foldable triangular map we are looking for.

Edges inherit their Tait colors throughout this process. In the last step, the Eulerian triangulation generated by dualization has just two edge colors incident to each node. Picking the third color to color each node gives a tricoloring.

A nearly physical folded configuration for the hemioctahedron (a pair of hinges must pass through each other) can be imagined as the folding onto a central triangle numbered 0, of three "ear" triangles, numbered in order of folding, 1, 2, 3.

This scheme gives us already one hinge on each side of the stack of triangles—thus we have no choice in hinging together the remaining two edges on each side.

The parenthesis words describing the hinge connections on each side of the folded stack of triangles:

On the side where triangle 1 folds down: ( ) ( )

On the side where triangle 2 folds down: ( { ) }

On the side where triangle 3 folds dow: ( ( ) )

Thus only one side of the stack has a non-physical fold.

Completely foldable octahedron with Bassetti-style hinges

A completely foldable octahedron with Bassetti-style rubber band hinges and extra parts.

The Bassetti "Poly-O" style rubber band hinges work better for completely foldable models because they maintain accurate alignment after re-folding. Here the flaps are extended to form a triangular box closure in order to keep them folded flat. The triangle sides are 5 cm, the notches are 0.25" diameter holes centered on the triangle corners.

Making a completely foldable object

An equilateral surface is a closed surface composed of equilateral triangles connected edge to edge. Physicists have looked into the requirements for an equilateral surface to be able to fold down to a single triangle. The folding considered is both phantom (the material can pass through itself) and instantaneous (no worries about the intermediate states of the folding or the geometry of those intermediate states.) It turns out there is just one simple requirement for complete foldability: the triangulation must be node tricolorable, that is, we must be able to assign three colors to the nodes of the triangulation such that no edge has the same color at both ends.

From the viewpoint of constructing such a completely foldable surface, if we can assemble the surface from corner tricolored triangles (matching colors where triangles join) the completed surface will be completely foldable.

I have assembled some completely foldable models using cardboard and rubber band hinges.

The printed pattern is a node tricolored triangle grid. Print on 65-lb cardstock.

Press onto a thoroughly gluestick coated poster board. Allow an hour to dry.

Trim along triangle edges.

Separate triangle strips.

Separate triangles.

Punch indicated hole positions with an approximately 4mm diameter hole punch. This can be done in decks of two.

Trim along colored curves. This can be done in decks of two.

Using small scissors, make three cuts meeting in the center.

Use scunci miniature hair elastics. Unstretched, these are about 16 mm in diameter.

With the aid of a crochet hook, attach a single rubber band to make a hinge with an 'X' crossing on each side.

A completely foldable octahedron

Properties of Tait-colored graphs

[Much of this post and the previous one is drawn from Marijke van Gans' 2007 doctoral thesis, "Topics in Trivalent Graphs."]

A proper edge coloring of a graph is a coloring of its edges such that nowhere are two edges of the same color incident to a node. A proper edge coloring of a cubic graph using three colors is called a Tait coloring. (Note, that if a cubic graph has a Tait coloring, it may well have many.)

An example of a trivalent graph that does not have a Tait coloring is the Peterson graph.

Nearly all cubic graphs have a Tait coloring. The Petersen graph is an example of one that does not.

Because each edge in a Tait-colored graph belongs to two cycles of alternating edge colors, no graph with a bridge can have a Tait coloring. (More obviously, no graph with a self-loop can have a Tait coloring, but all such cubic graphs have a bridge as well.)

Every bicubic (bipartite cubic) graph has a Tait coloring.

Every Hamiltonian cubic graph has a Tait coloring.

Since nearly all cubic graphs are Hamiltonian, it follows that nearly all are Tait-colorable.

Every bridge-free, planar cubic graph has a Tait coloring. (A consequence of the Four Color Theorem.)

A Heawood node 2-coloring is a node-2-coloring of a plane (i.e., embedded planar) graph under the condition that the number of black and white nodes in every face cycle are equal mod 3. A bridge-free planar, cubic graph can be Tait colored if and only if it can be Heawood node-2-colored; hence, as a consequence of the Four Color Theorem, every bridge-free, planar cubic graph can be Heawood node 2-colored.

Properties of graphs and trivalent graphs

GRAPHS

A graph is the action of a bilateral, reciprocal relationship (example: friendship) on the members of a set (example: the characters in Jane Austen's novels.) Clearly, there is no natural drawing of a graph. Nonetheless, we can always contrive a drawing by arbitrarily assigning to each member of the set a distinct point in space, its node, and then drawing curved or straight lines, edges, between nodes whose corresponding set members are joined by the relationship.

The valence of a node is the number of edges that join to it. The valence of an edge—i.e, the number of vertices that are joined by it—is always 2. A graph is n-valent if all of its nodes have valence n.

We allow multiple instances of the relationship to exist between the same two members (parallel edges); and we also allow instances of the bilateral relationship to exist where both parties are the same individual (a self-loop.) (Note that the existence of either of these these situations will require us to use curved lines in drawing the graph.) A graph having neither parallel edges nor self-loops is called a simple graph. There is such an abundance of non-intersecting lines in 3-space that every simple graph can be drawn using straight lines intersecting only at the nodes. Curved lines allow all graphs to be drawn in 3-space. Graphs that can be drawn in 2-space using curved, non-crossing lines are called planar. 

In outline form, the hierarchy of graph classes is:

graphs (historically, pseudographs)

     multigraphs = graphs without self-loops

          simple graphs = graphs with neither self-loops nor parallel edges (historically, graphs)


A walk in a graph is an alternating sequence of nodes and edges such that successive pairs of nodes are indeed joined in the graph by the edge named between them. A walk can re-travel the same edge or pass through the same node any number of times. A trail is a walk where no edge is re-travelled. A trail where furthermore, no node is passed through more than once, is called a path. A cycle is a closed path (the node where a cycle both begins and ends is not considered to be passed through more than once.) A cleaner definition of a cycle is a connected 2-regular graph—see terms defined below. The length of a cycle is the positive integer that gives the number of edges in it—there is no such thing as a 0-length cycle. A cycle is termed odd or even as its length is odd or even. A graph with no odd cycles is called bipartite. In a bipartite graph the nodes can be properly bicolored, e.g. each node can be colored black or white such that no two nodes of the same color are joined by an edge. The length of the shortest cycle in a graph is its girth.

A graph is not necessarily all in one connected piece. The smallest number of walks that can span the graph (i.e., include every node) is k, the 0th Betti number, the number of components of the graph. A graph with k = 1 is termed connected.

A graph with no cycles is called a forest. A single component of a forest (i.e., a connected, acyclic graph) is called a tree. An edge that is not part of any cycle is called a bridge. Thus every edge in a forest is a bridge, and—having indeed no odd cycles—every forest is bipartite.

The minimum number of edges whose deletion reduces a graph to a forest is o, the cyclomatic number, or 1st Betti number of the graph.

o = m − n + k,

where, n is the number of nodes and m the number of edges.

The minimum number of edges whose deletion disconnects a graph is its edge connectivity. For example, the edge connectivity of a multicomponent graph is 0, while the edge connectivity of a connected graph containing a bridge is 1.

The minimum number of nodes whose deletion disconnects a graph is its vertex connectivity, or simply its connectivity.

Edge connectivity and vertex connectivity are rather different things. For example, a good strategy for edge-disconnecting a network of friends would be to break a friendship of a person with few friends in the network. In contrast, a good strategy for vertex-disconnecting a network of friends would be to remove from the network someone with many friends in the network.

A tree that spans a graph (includes every node) is called a spanning tree—a spanning tree is a connected, acyclic subgraph that spans the graph. Every component has a spanning tree.

A closed trail (no edges are re-travelled) that includes every edge in a graph is called an Eulerian circuit. If such a closed trail exists, the graph is termed Eulerian. A necessary and sufficient condition for a graph to be Eulerian is that the valence of every node is even.

A 1-factor, or perfect matching, is a 1-valent subgraph (i.e., a set of disjoint edges) that spans the graph.

A 2-factor is a 2-valent subgraph (i.e., a set of disjoint cycles) that spans the graph. If there exists a single-component 2-factor, the graph is termed Hamiltonian.

A graph is termed n-regular or n-valent (or zero-valent, monovalent, bivalent, triavalent, etc.) if every vertex has valence n.




TRIVALENT (3-REGULAR OR CUBIC) GRAPHS

A graph where the valence of every node is 3 (every node is the junction of three edges) is called 3-regular, trivalent, or cubic.

A zero-valent graph, or empty graph, is simply an unconnected set of nodes. A monovalent graph is a collection of disconnected line segments. A bivalent graph is composed of disconnected cycles. But, a trivalent graph may have great complexity. As we will see, any sort of graph, and all its embedding in two dimensional surfaces, can be studied in the guise of edge-colored trivalent graphs.

Every cubic graph has an even number of nodes. In particular, for any cubic graph there is an integer, h, such that n = 2h and m = 3h.

Every cubic graph is cyclic.

A cubic graph having a self-loop also has a bridge.

In a cubic graph with n>2, no edge can have more than one parallel.

In every cubic graph, edge connectivity is numerically equal to vertex connectivity.

The number of Hamiltonian cycles in a cubic graph is even.

If one Hamiltonian cycle passes through a given edge of a cubic graph, another Hamilton cycle passes through the same edge.

Nearly all cubic graphs are Hamiltonian  (i.e., the likelihood that a randomly chosen cubic graph will be Hamiltonian goes to 1 as n goes to infinity.)

Gems from gems

Action of the map dualities on the edge 4-cycles of a graph-encoded map.

From one graph-encoded map, five other gems are easily generated. The six mutually related gems are called direct derivates.

Recall that black-pink cycles in gems are special. They are always 4-cycles because they represent edges (edges must have exactly two ends) so we cannot make a move that turns black-pink cycles into any other sort of cycle for fear that what will be left (to turn into black-pink cycles) will not have cycles of 4.

We can, however, switch those two colors, black and pink. That will still leave us with a Tait-colored graph having black-pink cycles of length 4. But, in consequence of switching black and pink, the pink-white cycles transform into black-white cycles, and the black-white cycles transform into pink-white cycles. In other words, vertices have become faces, and faces have become vertices. This color switch is an operation of order two, since repeating the color switch just returns the original gem. The new gem encodes what is known as the (Poincare) dual of the original map.

There are four more possible permutations of three colors, but none of them is fair game because of the need to insure that we have black-pink cycles are of length 4. Nonetheless, we can still do some systematic re-connecting of the nest.

Tracing around a black-pink cycle, we can always label the vertices in the order they are encountered such that the colored cycle is:

(ab), {bc}, (cd), {da}

where parentheses are black edges and curly brackets are pink edges. The operation skew "cross-wires" the black segments to make the cycle:

(ac), {cb}, (bd), {da}

The result of skew is called the Petrie dual of the map. 

 The corresponding operation that "cross-wires" the pink segments is called phial, the result of phial is called the antimap. (Since dual allows us to switch colors at will, having a separate, color-specific operator for pink edges is not strictly necessary.)

Like dual, skew and phial are operations of order two: "cross-wiring" the same pair of edges twice leaves them in their original arrangement. Operations of order two are termed dualities.

Composing the three dualities discovered above (Du, Sk, Ph) yields two more operations we can perform on a gem: Sk(G*) and Ph(G*). These two composite operations are mutual inverses—each undoes the other. They are also trialities: applying either operation three times in succession returns the original gem.

Above is an incomplete Cayley diagram (the actions of the two trialities are omitted) that shows what happens to the black-pink 4-cycles under the action of the dualities. (Note the surprising fact that when one color is already crossed, the operation of crossing the other color is equivalent to simply rotating the diagram 90 degrees.)

What the heck are graph-encoded maps?

A wireframe model of an octahedron uses only 12 wires but fails to specify what surface is being described (in other words, the wireframe specifies the abstract graph, but not its embedding.)  A graph-encoded map of the octahedron needs 24 wires in each of three colors (72 in total), but succeeds in specifying the surface up to topological equivalence.

What has three colors, a wire of each color at each junction, and encodes a surface?

Graph-encoded maps (gems) are just the thing for anyone who would rather think about surfaces and maps visually rather than algebraically. This is a short introduction to graph-encoded maps for those who might be inclined to put them to use. It will be seen that understanding gems makes it easy to understand relations between maps that may seem at first perplexing, e.g., dual, Petrie dual, phial, antimap, etc. Deep insights like map permutations become almost obvious.

A graph is a collection of edges having vertices at both ends. We allow the same two vertices to be at the ends of multiple distinct edges (parallel edges) and we allow the same vertex to be at both ends of an edge (a self-loop.) A graph is not necessarily connected (it may have multiple components), but we will be dealing here exclusively with connected (single component) graphs.

A practical use for graphs, especially in computer graphics and generative art, is to describe and subdivide a surface. A proper embedding of a graph in a closed surface is a drawing of the graph on the surface without any crossing lines, and such that, if all the lines of the drawing were to dematerialize, the surface would fall apart into simply-connected pieces. (It follows immediately that only a connected graph can be properly embedded.) By requiring the surface to fall apart into simply-connected pieces we are requiring that the drawing have enough lines in the right places to fully reveal all the topologically significant details of the surface such as the presence of a handle or a cross-cap.

A map is a proper embedding of a graph in a surface considered up to topological equivalence.

A Tait-colored graph is a graph in which each edge has been assigned one of 3 colors, and every vertex has exactly three incident edges, one of each color. (It follows immediately that a Tait-colored graph cannot have a loop.) It turns out that we never have to deal with any other kinds of graphs if we don't want to, nor with any of their various embeddings in surfaces. Wilson (1979) and Lins (1982) found that anything we might say on these meaty subjects can be just as well expressed as Tait-colorings of abstract trivalent graphs. How simple!

Given a map, any drawing of the map on its surface is locally planar (topologically speaking) provided we stay within the scope of the simply-connected faces surrounding one vertex.  Staying within that limited scope, we can construct what is known as the barycentric subdivision of the map as follows.

We color the vertex at the center of our local scope with the 0-color because a vertex is a 0-dimensional component of the map. Here we identify the 0-color with BLACK.

We construct a mid-edge vertex on each edge incident to the (now black) vertex at the center of our scope (unless such a mid-edge vertex has already been constructed) and color these mid-edge vertices with the 1-color because an edge is a 1-dimensional component of the map. We identify the 1-color with WHITE.

We construct a mid-face vertex in the middle of each face surrounding the black vertex at the center of our local scope (unless such a mid-face vertex has already been constructed) and color these mid-face vertices with the 2-color because a face is a 2-dimensional component of the map. We identify the 2-color with PINK.

Now we construct new edges connecting the (black) vertex at the center of our local scope to its surrounding (pink) mid-face vertices, and also construct new edges connecting the mid-face vertices to the (white) mid-edge vertices within the scope (if such edges have not already been constructed.)

By repeating this construction for each vertex, what emerges is a new map, an Eulerian triangular (triangle-faced) map of the same surface (it is Eulerian because an even number of edges—and triangles—meet at each vertex.) In particular, the number of triangles meeting at each white, mid-edge vertex is 4; the number of triangles meeting at each pink, mid-face vertex is twice the number of original sides on that face; and the number of triangles meeting at each black, original vertex is twice the number of original edges meeting at that vertex. Every edge in this new triangular map connects vertices of two different colors, so each edge can be systematically colored using the third color, the color not present at either of its endpoints.

The dual of this Eulerian triangular map is a simple map (meaning three edges meet at each vertex) having an even number of sides in each of its faces. We can automatically generate a Tait-coloring for the edges of this map by allowing edges to inherit the color of the dual edge.

Using the "good 'n plenty" coloring scheme (0 = black, 1 = white, 2 = pink), every black-white cycle in a gem is a face, every pink-white cycle in a gem is a vertex, and every black-pink cycle in a gem is a 4-cycle representing an edge. Here, the gem—an abstract graph—is shown co-embedded with the original map (a barely visible triangulation) that it completely describes.

Now comes the good news: we can discard at this point the original map, graph, and surface. All can be reconstructed (up to topological equivalence) from the Tait-colored abstract graph—a "bird's nest" in three colors of wire—which is known as a graph-encoded map or gem.

A graph-encoded map of the tetrahedral graph embedded in a sphere (realized in Flexeez.)

Still the same gem. 

Recovering the map

To make a physical model of the surface encoded by a gem (a tricolored "bird's nest"):

1. Give each vertex in the "bird's nest" a number.

2. Cut out an equilateral triangle of mylar drawing film, one for each numbered vertex (if you find that your surface is non-orientable, you will need "ghost mylar" that passes through itself without difficulty.) Mark the vertex number in the center of the triangle, and draw black, white, and pink perpendiculars to the sides. Either of the two possible cyclical orders will do: black-white-pink or black-pink-white. (Since mylar is translucent, we can always flip a triangle over to switch the cyclical order when needed.)

3. Trace the wiring in the "bird's nest" to find the numbers of the black, white, and pink neighbors of each numbered vertex, and so label the correspondingly-colored perpendiculars on its triangle.

4. At this point, no further reference to the gem or "bird's nest" is needed. Assemble the triangles edge-to-edge in accordance with their labels.

An exchange move that preserves tricolorability

Edge-coloring of the connectivity map for the completely foldable triangle grid.

When the edges of the connectivity map are colored the same as the edges of the triangulation (the triangle edges being colored with the mean of the node colors at each end,) left-right, geodesic paths (Petrie paths) cycle through three colors, and facial cycles cycle through two colors.

By shifting branches past each other two-past-two, and then swapping the colors of two edges, a doubled exchange can be made that preserves tricolorability.

An exchange move that preserves tricolorability.

An expansion move that preserves complete foldability

An expansion move that preserves the tricolorability (complete foldability) of  a triangulation.

Like the Pachner moves in the previous post, the composite move that preserves the tricolorability or tripartite-ness of a triangulation has a dual version that acts  on the trivalent connectivity map.

The expansion move acts on the dual connectivity map (dashed lines) in a predictable way.

Expansion in the connectivity map is simply the insertion of a digon in an edge. This increases face count by one, vertex count by 2, edge count by 3.

Expansion in the connectivity map is simply the insertion of a digon in an edge.

Moves that preserve the tricolorability of the triangulation preserve the local bipartite-ness of the connectivity map.

Exchange and expansion: Dual versions of the Pachner moves

Expansion and exchange moves, dual versions of the Pachner moves. Image quoted from Bilson-Thompson et al., "Update on braids and preons."

Each of the Parchner moves (and their compositions) has an equivalent in the dual map, the 3-regular (a.k.a., trivalent or cubic) map that directs the connectivity of the triangles in the triangulation.

Exchange = dual version of flip₂₂ = Find a 3-edge path that turns left-then-right or right-then-left. Slide the two non-path, branch edges past each other. Leaves the face, vertex, and edge counts unchanged. In fullerene chemistry this is the Stone-Wales transformation.

Expansion = dual version of flip₁₃ : truncate a (trivalent) vertex, creating a trianglular face in its place. Increases face count by 1, vertices by 2, and edges by 3.

Contraction = dual version of flip₃₁ = contract a trianglular face, leaving a trivalent vertex in its place. Decreases face count by 1, vertices by 2, and edges by 3.

Mutating completely foldable triangulations

If we have a completely foldable (CF) triangulation in hand, we might be able to mutate it into another CF triangulation by making local "moves" that preserve its tricolorability.

It is known that a sequence of Pachner moves (a.k.a., bistellar flips) connect any two triangulations of the same surface.

The three Pachner moves are:

flip₂₂ = rotate the edge shared by two triangles (this move is self-inverse.)
flip₁₃ = trisection one triangle into three triangles by adding one vertex and three edges to its interior.
flip₃₁ = weld together the three triangles around a trivalent vertex by removing the vertex and its three incident edges (this is the inverse of flip13.)

None of the Pachner moves preserve the tricolorability of a triangulation by themselves. Rotate creates four non-Eulerian vertices when applied to a triangulation that is already tricolorable. Trisection does the same. Weld cannot even be applied to a tricolorable triangulation since it needs a trivalent vertex. 

The tricolorability-preserving mutation we are looking for, if it exists, must be expressible as a composition of Pachner moves.

There are nine possible 2-move compositions of Pachner moves, and these may have variations depending on which edge or triangle we choose operate on in the second move.

We can immediately eliminate the 2-move compositions that begin with weld since there are no trivalent vertices to be found in a triangulation that is tricolorable. For like reasons, we can eliminate the 2-move compositions that end with trisection since this would leave us with a trivalent vertex in the triangulation making it non-tricolorable.

The three remaining possibilities are:

rr: rotate-then-rotate: an identity when the same edge is operated on in the second move; the first rotation creates four non-Eulerian vertices and there is simply no way to repair them all with a subsequent rotation of any other edge.

rw: rotate-then-weld: this fails in the general case because there is no guarantee that the edge rotation of the first move will produce a trivalent vertex to weld in the second move. The special cases when an edge rotation produces a trivalent vertex are: I, when at least one of the vertices the edge rotates away from has valence 4, and II, when at least one of the vertices the edge rotates toward has valence 2.

tr: trisection-then-rotate: this works any time the rotation acts on one of the three edges created in the first move. Rotating some other edge in the second move would leave a trivalent vertex from the first move, making the triangulation non-tricolorable.

tw: trisection then weld: this is an identity since the only trivalent vertex available to weld is the one created in he first move.

So the only 2-move composition of Pachner moves that preserves tricolorability is tr, more explicitly, "trisection a triangle, then rotate one of the new edges." The action of tr is to increase the count of vertices by 1, faces by 2, and edges by 3.

In visual terms, tr parallellizes an edge and then separates the two parallel edges with a bisected edge.

With hindsight we can construct an inverse for tr from special case II of rw as follows. If any vertex in a triangulation has valence 2, it must lie between two parallel edges (else its incident faces could not both be triangles.) Finding such a 2-valent vertex, we can rotate either of its opposing parallel edges, making said vertex 3-valent, and then remove the vertex with weld. Note that this rw acts as the inverse of tr regardless of which of the two opposing parallels gets rotated and ultimately removed.

That gives us tr, which can grow a tricolorable triangulation, and rw, which can shrink one, leaving us still in the hunt for a mutation that can interconvert tricolorable triangulations of the same size.

What tr means physically is that we slit open one edge of the triangulation (creating the two parallel edges) and repair the wound by gluing on a triangular envelope that has been likewise slit open one on edge. The net result is that we have joined a triangular "ear" to the surface. The 2-valent vertex is the point of the ear. Inversely, rw finds such an ear and removes it.

Clearly, slit-and-join is a general technique we can use to compose any two completely foldable triangulations (CFT's) along a doubled common edge. If we imagine this surgery occurring when both CFT's are completely folded, the final move is simply to fold on the coincident common edges so that we once again have a single triangle.

Generating completely foldable triangulations

Tripartite subdivision of an icosahedron.

When the triangles of the above mesh are made equilateral, the resulting polyhedron (a stellation of the rhombic triacontahedron) is completely foldable. The paper model itself is rigid, but the surface has an alternate conformation as a stack of triangles.

As shown by Di Francesco and Guitter, the necessary and sufficient condition for a closed surface composed of equilateral triangles to be completely foldable is that its graph is tripartite. Given a surface mesh (or, topologically speaking, a map,) they teach a simple way to generate a tripartite triangulation (triangle-faced map) of the same surface.

Construction: Given a map with black vertices, bisect every edge with a white vertex; place a pink vertex in the center of each face and connect it to the white and black vertices incident to that face.

The construction is equivalent to the map operation Meta (a.k.a. barycentric subdivision, full bisection, 2-D subdivision, dual triangle quadrisection,) and as well the construction that locates the preimages of 0, 1, and ∞ in a dessin d'enfants.

Completely foldable surfaces

What kinds of closed, triangulated surfaces can be completely folded up into a single triangle?

The classic interest of origami is folding up a portion of the plane (usually a square sheet of paper) into a more appealing or useful shape, but physicists interested in 2-D quantum gravity have been looking at folding from a different direction: what kinds of closed, triangulated surfaces can be folded up into a small triangular portion of the plane?

Di Francesco and Guitter have shown that any vertex-tricolorable mesh of equilateral triangles can be phantom-folded to a single triangle. By phantom-folding we mean that the surface is allowed to pass through and coincide with itself in its folded state; by vertex-tricolorable (a.k.a., properly 3-colorable, or tripartite) we mean that we can assign one of three colors to each vertex of the mesh such that no two adjacent vertices receive the same color. When completely folded into a single triangle—or even just partially folded onto the plane—we find that the coincident vertices share the same color. Di Francesco and Guitter's result holds for any genus of surface, orientable or not.

Vertex-tricoloring a triangulation is rigid: coloring the three vertices of a single triangle forces all the rest. The coloring goes easily or not at all. The underlying graph must be tripartite for the coloring to succeed. Whenever an equilateral triangulation folds onto a portion of the plane, it has three vertex classes, and their spatial arrangement will conform exactly to a vertex tricoloring of the plane equivalent to this one. A subsidiary tricoloring of edges (not a proper edge coloring) results by simply mixing the vertex colors of each edge's endpoints. This edge coloring does direct a proper edge coloring of the dual, trivalent graph that describes the triangles' connectivity.

A surface mesh composed of equilateral triangles necessarily gives a rather crinkled approximation to a smooth surface (see image below.) Adding a requirement of vertex-tricolorability exacerbates this. A necessary (but not sufficient) condition for vertex-tricolorability is that there be an even number of triangles around each vertex. (Place three—or any odd number—of equilateral triangles around a vertex and try folding the ensemble flat!) That means surface curvature can only be coded by clusters of 6, 4, 8, etc., equilateral triangles around a vertex—we forfeit the option to approximate surface curvature with clusters of 3, 5, 7, etc., triangles. Completely foldable surfaces will in general look quite crumpled even in their fully extended state. C'est la vie.

A surface composed of equilateral triangles is crinkly-looking even before we require the triangulation to be Eulerian (i.e., to have an even number of triangles around each vertex, such a triangulation is locally tripartite.) Image quoted from Isenburg, Gumhold and Gotsman, "Connectivity Shapes."

By the way, to physicists, the curvature we are talking about is the quantized gravitational curvature of a 2-D spacetime, a curvature induced by the presence of matter. Constraints that we may find vitally useful (i.e., foldability) sometimes just make for more interesting behavior in their models.

Phase-correcting splices in puck weaving

A phase-correcting splice in puck weaving.

If an error is made, or the basket weaving is improvisational, the problem arises of joining two out-of-phase sections of composite weaver. These situations always arise in pairs—if you switch to the wrong phase in one place, you are going to have to switch back again before you come around the loop.

A way to do this is shown above. It does not compromise the strength, but adds one ply of thickness in two non-adjacent squares. Since corrections come in pars, each error causes one extra puck to be added to the work.

Puck weaving the dodecahedron

The skeleton graph of the dodecahedron is not bipartite, so, despite its high symmetry, making a dodecahedral basket is a project that introduces the real housekeeping chores of puck weaving.

We have a goal to finish at an all-outboard vertex in order to make the closing moves easy and familiar. More burdensome, we must keep track of all the Petrie paths in the basket to insure that we phase them consistently (i.e., should we place the next "unprecedented" puck centrally or outboard?). As far as the absolute phase goes, we only care about the three targeted Petrie polygons that intersect at our terminal vertex. For all the other Petrie polygons, we only care that we phase them consistently. Should we fail to do so we'll come to a non-sequitur in the weaving.

A vertex on the dodecahedron happens to have an antipodal vertex where the same three Petrie polygons also intersect. Since the half circumference of a dodecahedron (taking its Petrie polygons to be geodesics) is 5 edges, an odd number, an all-outboard vertex on the dodecahedron will always have an all-central vertex at its antipodes. Unfortunately, since we must keep track of the phases of all of the Petrie polygons anyway, this property does not really make the puck weaving of a dodecahedron any easier. 

The best working method seems to be to mark up an undip word for the dodecahedron with the correct phasing of the "unprecedented" weaver to be added at each open letter. Since central phasing seems a natural default, I mark open letters with a prime if the phasing of the unprecedented weaver is outboard. The whole weaving must be calculated in advance to get this right. Below is an example worked out by hand for the dodecahedron.

The three Petrie polygons that intersect at a vertex on the dodecahedron also intersect at its antipodes.

The phasing of all of the Petrie polygons must be calculated before weaving can begin. The pink line marks the Hamilton path traced by the undip word. The Petrie paths follow the crossovers (half-twists) at the midpoint of each edge. Each Petrie polygon has been labelled with a consistent alternation of 'c' and 'o' phasing (central and outboard.)

The undip word with its housekeeping markup is unnndn'unu'uu'pppdpdpdd .

Aluminum puck-woven cube

This cube was not made using an undip sequence. The working was crowded due to the need to pre-bend the springy aluminum sheet metal to approximately the final angle of its diagonal folds. It proved more practical to complete an all-central vertex at the "south pole," secure it on the outside with duct tape, add all possible extensions to that vertex (6 of them), and then weave in an equatorial belt of 3 puck weavers. That accounted for all 12 pucks. All that remained was an all-outboard vertex to be closed at the "north pole."

Increasing the radius at the rounded corners to about 0.5 cm helped in closing the outer flaps at the last vertex. 

Puck weaving from undip words

When puck weaving from an undip word, we build out a triangulated surface one triangle at a time, one triangle per undip letter. Half of those letters are "open", the other half are "close" letters. 

Each finished triangle is 4 plies thick. Each 4-square puck weaver effectively covers 4 * 2/3 triangles with a single-ply thickness. So, on average, we need to add 1.5 unit weavers per letter. (That checks since there is one undip letter per vertex in the primal map, and we already knew that we need 1.5 unit weavers per vertex.)

A possible weaving strategy is to add 2 puck weavers at each "open" letter, and 1 at each "close" letter. As an exception, add 3 puck weavers at the first letter (which is invariably "open") and 0 at the last (which is invariably "close."). This strategy always yields  1.5 puck weavers per letter.

4-square puck weavers extend pretty far. One placed centrally extends half-way through it's neighbor's neighbor; one placed "outboard" extends (on its longer side) half-way through its neighbor's neighbor's neighbor. These long extensions can make puck weaving visually complex compared to simple unit weaving, so it is desirable to have definite placement rules to follow. 

Bipartite maps are the simplest to weave. If we always shingle composite weavers the same way (the standard way is with the leading strokes of the w's in front,) then every all-central vertex will be identical, and every all-outboard vertex will be identical. If the primal map is bipartite, then it is possible to have just these two types of vertex in the basket. Such a solution is found simply by making these two types alternate around any cycle, for example the Hamilton cycle encoded by an undip word. This alternation in types will occur automatically along the length of any composite weaver, we only need to be careful when placing crossing pucks to avoid creating a hybrid vertices.

If we would like an undip word for a bipartite basket to terminate at an all-outboard vertex, we simply need to start it at an all-central vertex. 

Each woven peak can be characterized as "upstairs" or "downstairs" by circling around the peak in a counterclockwise direction and noticing the "steps" where each weaver underlies or overlies the next. This determination can be made on either side of the fabric and gives the same result. When composite weavers are shingled the standard way (with the leading stroke of the w in front) only "downstairs" peaks are correctly woven. Weaving correctly automatically assures that the flaps of the pucks are hidden on both faces. 

Oriented weavers: teleological weaving

Kagome weaving. In polyphase unit-weaving each of these weavers would have a specified direction (orientation.)

Polyphase weavers have a structure similar to fallen-over dominoes. This structure gives the composite weaver a definite directionality or orientation.

Weaver paths can wander all over a basket, sometimes crossing over themselves. In some cases a single weaver constitutes the whole basket.

The weaving elements used in traditional basket making have an orientation—the direction that the plant material, say rattan or bamboo, grew—but it is not usually a concern in weaving. A composite puck weaver has an orientation too.  The structure of a composite weaver is like a row of dominoes that has fallen over. Just as we can tell in which direction the dominoes fell, the structure of a composite weaver has a definite orientation. Either orientation will work fine in the weaving, so orientation would not be a concern if we were to make the whole weaver in one step. The problem is that we will be building small portions of weaver at a time, and generally not knowing which weaver we are working on. The only solution is to have complete foreknowledge of the basket being woven so that the orientation of each unit weaver being placed can be specified.

When weaving by undip code, we add one triangle at a time to the completed work. The triangle depicts three segments of weaver. The orientation of two segments are already fixed because  they also appeared in the preceding triangle. If the letter for the triangle is a close letter, then the orientation of the third segment is fixed by its appearance in the older triangle that is being closed to. Thus the orientation of the weavers in puck weaving requires the addition of one bit of information to each open letter in an undip code.