Proving Weaving

The Plain-Weaving Theorem

Akleman, Chen, Xing, and Gross (ACXG) have published a proof that every polygonal mesh describes a plain-weaving (a term to be precisely defined below.) If so inclined, we may count two plain-weavings by considering weavings differing only in textile handedness (indicated by the helical pattern of threads around a specified opening in the fabric) to be distinct.

(Note that any weaving can theoretically be everted—turned inside-out—through an opening. While this does not alter the textile handedness of the work, it does change the handedness of the work as a whole. For example, eversion turns a right hand glove into a left hand glove. So it may fairly be said that the everted version does not weave the same surface. Nonetheless, the same set of weavers, woven in the same handedness, may weave either surface. The basket maker will need a hint to resolve this ambiguity.)

ACXG's result is fundamental. Their proof is fully three-dimensional and topological, so there can be no objections as to its physical reality. The proof leaves no escape for a compact surface of any sort -- all compact surfaces, be they orientable or non-orientable, high-genus or low, are doomed to be woven as baskets. The escapees are the non-compact surfaces, i.e., surfaces of infinite extent, or infinite topological genus, or having excluded interior points or open boundaries—but such are not buildable by any method.

And there is also no escape for any particular kind of mesh. Their result, which I will take to calling the Plain-Weaving Theorem (PWT,) states that all polygonal surface meshes describe a way to weave the surface. There is great difficulty imagining any way to subdivide a surface into local neighborhoods that is not in effect a polygonal surface mesh. Admit it or not, computer scientists are doomed to be virtual basket weavers for the rest of history.

Having this 3D theorem in hand, I want to turn to a purely 2D representation of plain weaving which is easy to visualize, easy to characterize as a mathematical object, and probably sufficient for all artisanal purposes.

The Definition of Plain-Weaving

I adopt ACXG's definition of plain-weaving—which differs from common usage in the textile field. In their definition, a plain-weaving "consists of threads that are interlaced so that a traversal of each thread alternately goes over and under the other threads (or itself) as it crosses them." This definition takes in some weaves such as the kagome (also known as open hexagonal or triaxial) weave that are not considered "plain" in the textile field, but the PWT rewards us with the insight that all plain-weaves newly defined are really the same thing and can be intermixed freely.

Weaving and Chess-Colorings

Kenneth Snelson, in the specification of his patent on 3D weaving, U.S. Patent 6,739,937, makes a significant observation: we can treat weaving as a 2D arrangement of openings rather than a 3D arrangement of threads. To turn the old saw around, Snelson is saying we should watch the hole, not the donut.

As Snelson observes, the openings in a plain-weave fabric have a handedness that can be compared with the handedness of a screw-thread. In going from over-one-thread to under-the-next whilst going around an opening, the threads have a ramp-like geometry. If we arbitrarily choose a direction of travel around the periphery of the opening, and identify that direction with the direction of the curled fingers, then using the ramps in this direction converts the advancing movement into a motion in a perpendicular direction. We can identify this perpendicular direction with the direction of the thumb extended. Uniquely only a left or a right hand is capable of carrying both of these identifications. We can therefore unambiguously label every opening in a weave as right or left, R or L, or perhaps color code them black or white. Since no reference has been made to a side of the fabric, the handedness of the openings is intrinsic to the weaving: it matters not which side we view or whether the work is everted or not.

Also, there can be no question that the threads in a plain-weave agree on the handedness of any opening they share—otherwise they would not be able to reach a mutual arrangement about whose turn it is to go over or under where they cross. Like a circle of fallen dominoes, they must all lean one way.

Snelson observes that adjacent openings (i.e., openings on opposite sides of the same thread) have opposite handedness. This follows almost anatomically: if two hands have curled fingers pointing in the same direction, and extended thumbs pointing in the same direction, they surely must be a right and a left.

A coloring of the faces of a map with two colors, say black and white, such that adjacent faces have different colors is called a chess-coloring (I prefer this shorter term over "checkerboard coloring") Not all maps can be chess-colored, but a map operation, medialization, is known which converts any map into a chess-colorable map (Deza and Dutour.) The resulting map is called the medial of the original map (itself called the primal), and the result of medialization is the same whether we start from the primal map or its dual. In map operation notation (see Diudea et al. for an explanation of the notation):

Me(M) = Me(Du(M))

This is the result reported in ACXG that a mesh and its dual describe the same weaving. As Deza and Dutour have pointed out, medialization can be applied to any map (surface-embedded graph) to produce a chess-colorable map, hence every surface-embedded graph has a plain-weaving discoverable through this map operation.

In knot theory terms, a plain weaving is an alternating link. The medial graph is the projection (or more properly the shadow when crossing information is omitted) of an alternating link. The chess-coloring of the medial graph corresponds the checkerboard-coloring of the link projection, and the primal and dual maps above are the two Tait graphs of the link projection (see explanation of terms in Dasbach and Lowrance.) Because the link is alternating it is described in full by its chess-coloring.

Mathematically the study of plain-woven baskets reduces to the study of chess-colorings on surfaces, and such a chess-coloring contains essentially all the information the weaver needs to weave the basket.

References:

Akleman, E., Chen, J., Xing, Q., and Gross, J. L. 2009. Cyclic plain-weaving on polygonal mesh surfaces with graph rotation systems. ACM Trans. Graph. 28, 3 (Jul. 2009), 1-8. DOI= http://doi.acm.org/10.1145/1531326.1531384

Snelson, K., U.S. Patent 6739937, Space Frame Structure Made by 3D Weaving of Rod Members.

Deza, M., and Dutour, M., Zigzags and central circuits for 3- or 4-valent plane graphs, http://www.liga.ens.fr/~deza/Sem-ZigCc/ZigCcConf.pdf

Diudea, M., et al., 2003, Leapfrog and Related Operations on Toroidal Fullerenes, Croatia Chemica Acta, 76 (2) 153-159, http://pubwww.carnet.hr/ccacaa/CCA-PDF/cca2003/v76-n2/CCA_76_2003_153-159_diudea.pdf

Dasbach, O. and Lowrance, A. 2010. Turaev Genus, Knot Signature, and the Knot Homology Concordance Invariants, http://arxiv.org/pdf/1002.0898