Graphs, Polygons, Nets and Polyominoes
Prepared by:
Joseph Malkevitch
Department of Mathematics
York College (CUNY)
Jamaica, New York 11451
email:
jmalkevitch@york.cuny.edu
web page:
http://york.cuny.edu/~malk/
Figure 1 shows a diagram that can be thought of as what one obtains when a particular spanning tree of the edge-vertex graph of a metrical 1x1x1 3-dimensional cube (3-cube) is cut and the cube is "opened up" and unfolded into the plane. The vertices of this diagram are labeled with the numbers 0 to 13.
It is instructive to think of this diagram from different geometric points of view:
a. Figure 1 is a graph. From this point of view Figure 1 is not regarded as a metrical diagram but as a "combinatorial" object.
b. Figure 1 is a plane graph because it has been embedded or drawn in the plane so that edges only meet at vertices. From this point of view Figure 1 is not regarded as a metrical diagram, but it has faces in addition to vertices and edges.
c. Figure 1 can be regarded as a polyomino, in fact, a hexomino, a collection of six 1x1 squares where the squares only adjoin each other along segments of length 1. Note that the squares in Figure 1 meet edge-to-edge. From this point of view Figure 1 is a metrical diagram, but all the combinatorial information is there to be used.
d. Figure 1 can be regarded as a plane polygon with 5 diagonals of that polygon drawn. From this point of view Figure 1 is a metrical diagram. How many sides are there in the polygon shown? There are 14 sides, and 14 vertices. Note that at vertices 7 and 10 there are straight angles. Thus, we have the consecutive vertices 6, 7, 8 which lie on a single straight line. In fact, 0,1, 6, 7, and 8 lie on a single straight line. While vertices 4, 1, 2, and 13 lie on a single straight line, no three vertices which are consecutive lie along a single straight line!
e. Figure 1 can be regarded as a "net" of a cube. The term net is usually used to refer to a plane polgyon with diagonals indicated so that when one treats the diagonals as fold lines, one can match up edges which make up the boundary of the polygon to obtain a polyhedron. Unfortunately, the situation is not as simple as this, as was first observed by the British mathematician Geoffrey Shephard. He noticed that without specifying which edges are to be pasted (glued) to which along the boundary, when the fold lines indicated are "respected" there may be more than one polyhedron that can be obtained by using different choices for the edges that are identified with each other. An example of this phenomenon, involving a polygon which can be subdivided into equilateral triangles, is shown in Figure 2. This "net" can be realized by both the regular octahedron and a non-convex "deltahedron" - a polyhedron in 3-dimensional space all of whose faces are equilateral triangles - known as the "boat." For some "nets" one can get two inequivalent convex polyhedra by gluing different collections of edges.
For the 11 hexaminoes which will fold to a 3-cube there is only one polyhedron each hexamino will fold to (the 3-cube) using the diagonals (fold lines) within the boundary polygon of the hexamino as the fold lines.
Figure 2 can be thought of as arising from the diagram in Figure 1 by erasing the line segments (diagonals) in the interior of the simple closed curve 0, 1, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 2, 3, 0.
Figure 2 can also be regarded as a graph or plane graph, and also as a polygon. But having erased some of the line segments from Figure 1, depending on formalities, it no longer shows the "full" square cells that show that it is a polyomino, more specifically, a hexomino. Again, a hexomino is a polyomino that involves 6 square cells. Some hexominoes fold to a 3-cube and some do not. The number of hexominoes is 35 but of these only 11 will fold to a 3-cube. For 7-ominoes, there are either 107 or 108 depending on whether one allows holes in one's definition of polyomino. The number of different polyominoes increases rapidly with the number n of cells. Thus, for n = 15 there are 3,426,576 polyominoes with holes allowed but only 3,001,211 if holes are banished. (Polyominoes are usually considered the same if they are congruent but if one counts "left" and "right" handed polyominoes as different one gets different counts. The important thing to notice is that mathematics thrives on distinguishing new or old objects from different points of view.
If we suppress the vertices in Figure 1, regarded as a polygon, which occur at vertices where there is a straight angle, we get the diagram in Figure 3. This polygon has 12 vertices (which have labels but the numbers are not consecutive) but the sides of this polygon (considered metrically) are different from the lengths of the sides of the polygon (considered metrically) in Figure 2.
We can again think of Figure 3 as a plane graph or polygon. Again, however, now the polygon has only 12 vertices. Figure 4 is the same metrical polygon as in Figure 3 but with the labels on the vertices deleted.
We can apply Alexandrov's Theorem to Figure 4 as we can to any plane non-self-intersecting metrical polygon P. Intuitively, this theorem says that if we identify all of the boundary points of a plane polygon in such a manner that:
a. All of the boundary is matched to itself
b. At no point of the gluing are there matched points where the sum of the angles at the "identified/matched" points exceeds 360 degrees
c. The topology of the resulting object (when not flat) is like a sphere or in more technical language the result is homeomorphic to a sphere
then the result is, amazingly, either a double covered convex polygon or a convex 3-dimensional polyhedron.
It takes experience to understand Alexandrov's Theorem fully. Thus, while we know (from the fact that Figure 1 arises from unfolding a 3-cube) that Figure 3 can be folded back to a cube. The unexpected reality is that Figure 3 can be folded into a variety of edge-to-edge things that are not cubes when Alexandrov's Theorem is applied. There are 5 different such foldings, and if we allow non-edge-to-edge "gluings" we get 85 additional types, of which 22 are combinatorially different and different from the cube!
References:
Alexander, R. and H. Dyson, J. O'Rourke, The Convex Polyhedra Foldable from a Square, in Proceedings of the Japan Conference on Discrete and Computational Geometry, Lecture Notes in Computer Science, Vol. 2866, Springer, New York, 2003, pp. 38-50.
Demaine, E. and J. O'Rourke, A Survey of Folding and Unfolding in Computational Geometry, in Combinatorial and Computational Geometry, (eds.) J. Goodman, J. Pach, and E. Welzl, MSRI 52, Cambridge U. Press, New York, 2005, pp. 167-212.
Demaine, E. and J. O'Rourke, Geometric Folding Algorithms: Linkages, Origami, Polyhedra, Cambridge U. Press, New York, 2007.
Golomb, S., Polyominoes, Revised edition, Princeton U. Press, Princeton, 1994.
O'Rourke, J., Folding Polygons to Convex Polyhedra, in Understanding Geometry for a Changing World, 71st Year Book, NCTM, (ed.) T. Craine and R. Rubenstein, NCTM, Reston, Virginia, 2009, pp. 77-87.
O'Rourke, J., How to Fold It: The Mathematics of Linkages, Origami, and Polyhedra, Cambridge U. Press, 2011.