Thursday, April 18, 2013

Most fabric techniques can make every orientable surface

The world offers many examples of closed surfaces, some of them rather daunting to the basket maker. Beyond weaving, there are several other fabric techniques that can make baskets: knitting, crochet, linking, looping, net tying, macrame, balloon tying, etc. So the question arises, "What fabric techniques can make which closed surfaces?"

The heartening answer is that most fabric techniques can make every orientable closed surface. This answer holds true even if we restrict ourselves to working with a single length of yarn that is spliced to itself, end-to-beginning, at the conclusion of the work.

Math Preliminaries

A graph is a set of vertices, some pairs of of which are connected by edges. In a general graph (the only kind of graph that concerns us here) an edge is allowed to connect a vertex to itself, and as well, an edge is allowed to connect the same two vertices as some other edge.

General graphs are usually represented diagrammatically with vertices drawn as dots on a surface, joined by edges drawn on the surface as curved lines. Whenever we draw a graph in this way, we are imposing a cyclic ordering of edges around each vertex, an ordering that is not intrinsic to the abstract graph. A graph, together with a surface, and a cyclic ordering of edges at the vertices that allows it to be drawn on the surface without edges crossing is called an embedding. An embedding is called proper if deleting the points under the drawing would cause the surface to fall apart into a topological disk or disks.

Not topological disks.
Topological disks.

What's a topological disk? For example, a disk containing a handle, or an interior hole, or an interior slit, is not a topological disk; but a sphere with a hole, or a slit, or a disk having a slit in its periphery, is a topological disk.

Neither graphs nor surfaces are necessarily connected, but, by a sensible convention, a "properly embedded graph" always means a one-component graph properly embedded in a one-component surface.

A surface is orientable if it is possible to make a consistent choice of surface normal vector at every point. Non-orientable surfaces, such as a Klein bottle, can only be tiled with truchet tiles if flipping tiles over makes no difference—most truchet tiles for fabric structures are not like that, so we are mostly limited to making orientable surfaces. That is a big disappointment mathematically, but perhaps of little practical importance (there's a good reason why nothing ever comes packaged in a Klein bottle.)

An orientable surface.

A non-orientable surface—a Klein bottle.


Every properly embedded graph (call it the primal) has a properly embedded dual. The dual has the same number of edges as the primal, but they have been, so to speak, rotated by about 90 degrees, so that they connect at the center of faces they once went around, and go around vertices where they once connected. In effect the role of the edges is maintained, while the roles of vertices and faces are exchanged. As implied by the name, this relationship is reciprocal: the primal is the dual's dual.

Superposition of any primal with its dual implicitly cuts the surface into quadrilaterals. (Visualize the two positions of  each edge as the two diagonals of a quadrilateral.) This is a well known mathematical fact, but its enormous practical significance is under-appreciated: every surface (or, at least, every orientable surface) is a playground in every possible way for any technology that can be described by a quadrilateral truchet tile. As we will see, there are a lot of technologies that want to play at this game.

Quadrilateral Truchet Tiles

Quadrilaterals are not generally squares, of course, but our truchet tiles need to be stretchy enough to accomodate the shape of any quadrilateral. With that understanding, there is no harm in idealizing both the quadrilateral truchet tiles and the surface quadrilaterals they will be placed on as being squares.

A surface quadrilateral idealized as a square.
As shown above, each of the surface quads has a primal diagonal terminated by primal vertices, and a dual diagonal terminated by dual vertices. The primal edge corresponds to one of the original graph (i.e., one of the cuts that divided the surface into topological disks.)

We will assume an oriented surface, so there is never any confusion in playing our truchet tiles "right side up." That still leaves four possible ways to rotate a quadrilateral tile when placing it on the surface. Of course, if a particular truchet tile has 4-fold rotational symmetry, there is no real choice, all four orientations are equivalent.

In the other cases, if the truchet tile has a designated primal diagonal, we may find that this primal diagonal has been played parallel or perpendicular (loosely speaking) to the primal edge of the surface quadrilateral. If the truchet tile has 2-fold rotational symmetry, there's no need to inquire further: a 180 rotation will make no difference.

In the other cases, if the primal diagonal of the truchet tile has been oriented, and likewise the primal or dual edge in the surface quad (whichever lies under the tile's primal diagonal) must have an orientation, so that we can speak of the tile being placed in a co or anti orientation to the underlying surface quadrilateral.

Working Order

In weaving we generally do not care how many threads (weavers) will be used, or in which direction they are to be laid in, but in most other fabric-making techniques it is desirable to work with a single thread, one that is consistently oriented from start to finish. That implies playing our game with truchet tiles having oriented primal diagonals, and placing them in a sequence that corresponds to the start to finish passage of the single thread.

A reliable way to find a route over the surface for the single thread is to find a subset of the graph of primal edges that forms a spanning tree, that is, a connected, acyclic graph containing all of the primal vertices. Finding a spanning tree in a graph is an easy task. One algorithm is to add some new vertex to the empty tree and try to add every incident edge, excepting only those that connect to a vertex already in the tree (as that would constitute a cycle.) Repeat for all the newly added vertices...etc. When no more edges can be added, the spanning tree is complete. Another algorithm, one easier to do by eye, is to begin with the complete graph, erase any edge that is part of a cycle, repeat until no cycles are left.

A spanning tree effectively colors every surface quadrilateral as tree or non-tree.

Running the thread in a way that does not cross edges in the spanning tree, but always crosses edges that are not in the spanning tree, yields a serpentine loop of thread that visits the entire surface.

In the following the primal diagonal of each truchet tile is chosen so that a proper placement of a tile is parallel in the tree quadrilaterals and perpendicular in non-tree quadrilaterals.

(To be continued.)

No comments: