Tuesday, August 31, 2010

Embedded graphs come in families of four

Cubic graph (the dual)
Triangulation (the primal)
Radial graph
Medial graph
Kagome weave
Anyam Gila
In unit weaving we are constantly dealing with families of four closely related graphs: a triangulation (the primal graph), a cubic graph (the dual graph), a medial graph, and a radial graph. Kagome (triaxial weaving) is closely related to the medial graph of a triangulation. Anyam Gila (or "mad weave"), a triple-layered version of kagome, has an outward appearance that suggests the radial graph of a triangulation.

Some facts from the Handbook of Graph Theory:

1. An embedded graph M is a medial graph of some graph G if and only if M is 4-regular and the faces can be properly 2-colored.

2. An embedded graph R is a radial graph of some graph G if and only if R is bipartite and every face is a quadrilateral.

3. The medial graph M of an embedded graph G is identical to the medial graph of the dual G*. The radial graph R of G is identical to the radial graph of the dual G*. The embedded graph and its dual are the only two graphs whose medial and radial graphs are M and R respectively.

Any surface-embedded graph can play the role of "primal," and it is guaranteed to have a dual, medial, and radial, all of which are discoverable through simple constructions called map operations. It is a convenience of speech that we identify one graph as the primal and the other as the dual: the roles could just as easily be reversed with no effect on the rest of the foursome. The same, however, is not true for the medial and radial (which are also mutually dual,) because radial graphs and medial graphs each have special characteristics as indicated in Facts 1 and 2 above. Thus, most graphs belong to only one foursome: the one formed when they are the primal (or equivalently the dual.) The few graphs that qualify as medial (or radial) graphs belong as well to a second foursome: the one where they are the medial (or radial.)

The familiar square grid makes for a special case. It is dizzyingly at once self-dual, self-medial, and self-radial. This deep symmetry of the grid pattern helps explain why 10,000 years of biaxial weaving has not gotten us very far in understanding weaving more generally.

When plain weaving is not in some artificially arranged conformation, just two threads cross at each crossing. A graph of a plain weaving (crossings being represented by vertices and threads being represented by edges) is therefore four-regular (i.e., exactly four edges meet at each vertex.) That satisfies the first requirement in Fact 1.

The relevance of the second requirement in Fact 1 can be seen from an observation by Snelson (U.S. Patent 6,739,937), that each thread in a plain weaving is a boundary between a left-handed opening and a right-handed opening. Such an arrangement is only possible if the fabric openings can be properly 2-colored (such a coloring is popularly known as a chess-coloring or checkerboard-coloring.)

The necessary and sufficient requirements for a graph to be a medial graph are thus the same requirements necessary and sufficient for a graph to specify a plain weave: the 4-regular graph specifies the two-dimensional arrangement of threads, and the 2-coloring of its faces tells us which openings are to be left-handed or right-handed. The handedness of the openings, in turn, tells us how to arrange the threads at each crossing, in the third dimension, to produce a true plain weave.

In this light, Fact 1 establishes that every medial graph describes two enantiomorphic plain weaves (one for each of the two alternate left/right color assignments.)

In the same light, the converse assertion in Fact 1 (i.e.: if M is 4-regular and the faces can be properly 2-colored, then M is a medial graph) establishes that no plane weave exists that is not described by a medial graph.

In short, weaving has found the light switch after thousands of years of fumbling in the dark:

1. We now know that every compact surface can be plain-woven-- no matter the topological complexity or the orientability of the surface. (The term "compact" merely rules out some mathematically defined surfaces that cannot be realized by any technological means. In layman's terms we can plain-weave any surface.)

2. We can plain-weave that surface in essentially any pattern (we are not limited to familiar biaxial or triaxial weaves.) Any graph, any drawing of edges and vertices we choose to put on the surface, can direct the weaving via its medial graph.

3. We know constructively how to proceed in every case.

4. We know that our construction process is universal: there exist no other plain weaves but those described by medial graphs.

We have 1-3 above from the 2009 topological proof by Akleman, Chen, Xing, and Gross (see my earlier post Proving Weaving) I believe the universality result is new.

No comments: