Planar Graphs and Modular Origami

Thomas Hull Dept. of Mathematics University of Rhode Island Kingston, RI 02881-0816, USA
Modular origami has its roots in complex origami gure design. If a designer could not create the desired object with one piece of paper, several sheets might make the task easier. However, thanks mainly to the popular works of T. Fuse and K. Kasahara ( 4], 5]), people nowadays think of modular origami as using several, sometimes hundreds of pieces of paper to create various geometric forms. The charm of such origami is that simple, easy to fold modules can lead to very complex, intricate structures. Also, since more than one piece of paper is involved, one can experiment with the multitude of color patterns that are possible in any one modular origami work. In exploring such geometric structures and color patterns, a good understanding of 3-dimensional polyhedral geometry is needed. In this paper, we will discuss how such a geometric understanding can be reached via a branch of mathematics called planar graph theory.1 By examining speci c examples, we will show how studying planar graphs can lead to the generation of more complex modular origamis and touch upon the inverse direction as well: how studying modular origami can lead to a better understanding of planar graph theory. Such a corollation would certainly be valuable to educators, and the author himself has found modular origami a great source of ideas and inspiration in his own mathematical research on planar graphs.
1

1. Introduction

For a more rigorous introduction to graph theory, see 2] and 3].

connected by edges, but for completeness a technical de nition follows: De nition: A graph is pair ( ), where = f 1 2 g is a set of vertices and is a set of edges. Thus each edge 2 is of the form = ( ) and means that the vertices and are connected by an edge. Figure 2.1 shows examples of some graphs.
G V E V v v ::: vn E V V e E e vi v j vi vj

2. What is a planar graph? A graph is what mathematicians use to model networks. It consists of a collection of points, called vertices, which are connected by lines, called edges. Intuitively, graphs can be thought of as simply a bunch of vertices

v1

v1 v7 v2 v5

v2 v3 v6 v4

v5 v3

v4

Figure 2.1: Some graphs. A planar graph is a graph that can be drawn so that the edges only intersect at the vertex points. In Figure 2.1, the left graph is planar, while the right graph is not. (You might need to experiment with a pencil and paper to convince yourself of this fact!) Our interest is in planar graphs because they provide a natural way of studying polyhedra. Imagine a polyhedra (say, a cube) in 3-dimensional space. Surely it too can be thought of as simply a collection of vertices (the corners) connected by edges! Furthermore, we could take one side (a face) of this polyhedra and stretch it out, as if the edges were made of elastic, so as to embed the polyhedra in a 2-dimensional plane. Doing this turns the polyhedra into a planar graph, and any polyhedra can be embedded in the plane in this way. To get a better understanding of this, see Figure 2.2, where planar graph embeddings of the ve Platonic solids are shown. (The cube might be the easiest to visualize.)

Tetrahedron

Cube

Octahedron

Dodecahedron

Icosahedron

Figure 2.2: The Platonic solids in planar graph form. The study of planar graphs has a long history in mathematics, going back to the time of Euler (1736). As a result, there are many known facts about planar graphs. For example, Euler himself proved that if is the number of vertices, the number of edges, and the number of faces in a planar graph, then ; + =2 This is known as Euler's formula2, and since it applies to planar graphs, it also applies to polyhedra. But let us now turn our attention to speci c examples of how planar graph knowledge can help us design modular origami structures.
v e f v e f :

3. \Capped" polyhedra modules.

Many modular folds create versions of \stellated", or \capped" polyhedra. That is, the form they produce is a polyhedra with pyramids \capped" on each face. The result is usually a spikey-looking object. Some examples can be found in Kasahara 5]. After designing such a module that could produce capped versions of almost any polyhedra, the author wondered what was the fewest number of colors needed to \color" such an object. By a coloring we mean an
It is interesting to note that whenever I show Maekawa's Theorem to other mathematicians, their rst response is usually to try corollating it to Euler's formula. No real connection exists that I am aware of, but who knows?
2

assignment of colors to the faces of the capped polyhedra such that no two adjacent faces have the same color. Speci cally, this would be called a facecoloring of the polyhedra. This question can be answered rather easily using a speci c case of a theorem from graph theory called Brook's Theorem. To understand it, we must de ne the degree of a vertex in a graph to be number of edges coming out of that vertex. Brook's Theorem (cubic case): A graph is vertex-colorable in 3 colors if its maximum vertex degree is 3, unless it is the tetrahedron. Note that this is a theorem about vertex-colorings, i.e., an assignment of colors to the vertices of a graph such that no two vertices connected by an edge have the same color. Thus, one might ask, \How does this relate to face-coloring capped polyhedra?" Suppose we have a polyhedra which we wish to cap (i.e., place pyramids on each of its faces). If we think of this polyhedra as a planar graph, then the capping process amounts to placing a new vertex in each of the polyhedra's faces, and then adding edges connecting the vertices along the face to the new vertex (see Figure 3.1).

Figure 3.1: The capping of a face. In fact, if is a planar graph, let us de ne ( ) to be \capped." That is, ( ) is the new graph obtained by doing the capping operation shown in Figure 3.1 to every face of . Then notice that every face of ( ) will be a triangle, and this is true for any planar graph (polyhedra) that we start with. Now we wish to color the faces of ( ). Doing this would be equivalent to coloring the vertices of the dual of ( ). The dual of ( ), which is denoted ( ) , is the new graph obtained by reversing the roles of the vertices and faces of ( ). Vertices of ( ) will be faces of ( ) , and faces of ( ) will be vertices of ( ) . In technical terms, ( ) is the graph whose vertex set is the collection of faces of ( ), where two vertices of ( ) are connected
G C G G C G G C G C G C G C G C G C G C G C G C G C G C G C G C G

by an edge if and only if the corresponding faces in ( ) are adjacent (next to each other). Figure 3.2 demonstrates how the dual of the cube is the octahedron.
C G

Figure 3.2: (Cube) =Octahedron. But what kind of graph is ( ) ? Since each face of ( ) was a triangle, each vertex of ( ) will be of degree three! Thus Brook's Theorem tells us that ( ) is 3 vertex-colorable. Since each vertex of ( ) corresponds to a face of ( ), this proves that ( ) can be face-colored using only three colors. Another interesting fact is that the structure of ( ) can be understood very well, no matter what polyhedron is. Recall what it means to truncate a polyhedron, i.e., to chop o each corner, creating a new face where the corner used to be. In terms of a planar graph, this is equivalent to replacing each vertex of degree with an -gon, as illustrated in Figure 3.3. In fact, let us de ne ( ) to be the graph obtained by truncating all the vertices of .
C G C G C G C G C G C G C G C G G n n T G

Figure 3.3: The truncation of a vertex. It is left as an exercise to the reader to prove that if is the planar graph of a polyhedra, then ( ) = ( ) That is, the dual of the capped is congruent (the same as) the truncation of the dual of . This handy little fact means that to face-color a capped cube, for example, one could equivalently vertex-color a truncated octahedron.
G C G T G : G G

4. Cubic skeleton modules.

In the above section we saw how capped polyhedra are related to graphs in which each vertex is of degree 3. A graph with only degree 3 vertices is 5

called a cubic graph. Cubic graphs play a central role in planar graph theory (as we will see below), and it is interesting that many modular origami units are \cubic" as well. That is, we call a modular unit cubic if it takes three units to form a corner, or vertex, of the underlying polyhedra. The Sonobe unit (see 6]) is one example of a cubic unit. One large class of cubic modules are what Jennenie Mosley refers to as \zig-zag" modules. They involve accordion-pleating a square into thirds or fourths to create a strip. This strip then has \pockets" on both of its long sides. When the strip is folded to produce aps for these pockets, any one of a number of di erent modules can be the result. Three examples which can be folded from a square accordian-pleated into fourths are shown in Figure 4.1.
Type I (R. Neale) Type II (T. Hull)

Figure 4.1: Three zig-zag modules. These modules can be used to produce \skeletons" of polyhedra, i.e., the units play the role of the polyhedra's edges. Neale's type I module is the most in exible of the three. When three are interlocked, they force a rigid angle which can only produce the skeleton of a dodecahedron. Types II and III o er more variety. Type II can generate skeletons of any polyhedra with neither triangular nor square faces. McIntyre's type III unit produces only polyhedra in which every face has an even number of sides. One reason such modules are of interest is because they o er us a fun and easy way to explore edge-colorings of cubic planar graphs. An edgecoloring is similar to vertex and face-colorings one colors the edges of the graph so that no edges which meet at a vertex are of the same color. In a cubic planar graph, each vertex has three edges coming out of it, so one might hope that we could always get away with using only three colors to properly color a cubic modular structure. In fact, we can always get away with three colors, but it is by no means easy to see why. This problem, whether or not we can color the edges of 6

Type III (S. McIntyre)

a cubic planar graph with only three colors, turns out to be equivalent to the famous Four Color Theorem, a theorem with one of the most notorious histories in mathematics!3 Thus the possibility exists that by 3-coloring cubic modular works, further light might be thrown on the search for a short proof of the Four Color Theorem. How this could possibly happen is another matter. But consider the exercise of 3-coloring the edges of a dodecahedron, which can easily be realized using unit type I in Figure 4.1. When this done, the observant folder might notice that no matter how you color it, the pentagonal faces which are opposite each other always have the same color pattern! This fact is not easily noticed when coloring the edges of the dodecahedron on paper. Moving from edge-coloring to planar graph structure, consider the unit type II in Figure 4.1. This unit locks together quite well, and made the author wonder how large a structure could be made from such a unit. Of course, a dodecahedron could be made with 30 units, and, remembeing that this unit can produce any polyhedron without triangle or square faces, a soccor ball (truncated icosahedron) can be made from 90 units. But what else? There turns out to be a very easy way to start with the dodecahedron and generate an in nite class of polyhedra with only pentagons and hexagons as faces. Let be the planar graph of the dodecahedron. Then the dual is the icosahedron (see if you can convince yourself of this!), and thus ( ) is the soccor ball. But look at what this process did. Each face of is a pentagon, so each vertex of has degree 5. When this degree 5 vertex is truncated, it will produce a pentagonal face! Thus the operation ! ( ) preserves pentagonal faces (see Figure 4.2). But where did the hexagons present in ( ), the soccor ball, come from? Well, each vertex of has degree 3, which turns into a triangular face in . In ( ) every vertex of this triangle has been truncated, resulting in a hexagon face! Thus when we
D D T D D D D T D T D D D T D

3 The Four Color Theorem states that any planar graph can be vertex-colored using only 4 colors. It was an open conjecture for a hundred years, until Appel and Haken proved it in 1977 by breaking the problem down into 1936 cases and checking each of these by computer. Thus the Four Color Theorem was the rst \computer proof." See 8] and 9] for more information

peform ! ( ), each pentagon face remains a pentagon and each vertex becomes a hexagon.
D T D

Figure 4.2: The relation between and ( ). Then what will ( ( ) ) be? Each pentagon of ( ) will remain a pentagon, and a similar argument shows that the hexagons of ( ) will remain hexagons too. But each vertex (still of degree 3) of ( ) will create a new hexagon in ( ( ) ), thus producing a new, bigger polyhedra still having only pentagons and hexagons as faces. This process can be continued to produce an in nite family of such polyhedra. It is a simple exercise to show that if has edges, then ( ) has 3 edges. Thus, the number of type II units needed to create any of these structures is easy to calculate. The rst four are given in the below table. 30 units ( ) 90 units ( ( )) 270 units ( ( ( ) ) ) 810 units The author has constructed the third iteration sphere (810 units) from 2-inch and 3-inch paper. They hold together quite well.
D T D T T D T D T D T D T T D G n T G n D T D T T D T T T D

5. Conculsion?

We hope the reader is convinced by these examples that knowledge of planar graph theory can lead to a deeper understanding of polyhedral structure, and thus a deeper understanding of the potentials of modular origami. In fact, the author's experience has been that only after studying the links 8

between planar graphs and modular origami was he able to start designing modular units of his own. Also, we have only touched upon a few examples here. The reader is encouraged to explore the \hidden graph" structure underlying all modular origami works.

References
1] D. Barnette. Map Coloring, Polyhedra, and the Four-Color Problem, The Mathematical Association of America, (1983). 2] J.A. Bondy and U.S.R. Murty. Graph Theory with Applications, North Holland, New York, (1976). 3] G. Chartrand and L. Leskiak. Graphs and Digraphs, 2nd ed., Wadsworth & Brooks/Cole, Paci c Grove, (1986). 4] T. Fuse. Unit Origami, Japan Publications, New York, (1990). 5] K. Kasahara. Origami Omnibus, Japan Publications, New York, (1988). 6] K. Kasahara and T. Takahama. Origami for the Connoisseur, Japan Publications, New York, (1987). 7] A. Loeb. Space Structures, Addison-Wesley, Reading, (1976). 8] T. Saaty and P. Kainen. The Four-Color Problem: Assaults and Conquests, McGraw-Hill, New York, (1977). 9] R. Steinberg. \The State of the Three Color Problem" in Quo Vadis, Graph Theory?, Gimbel, Kennedy, and Quintas eds., Annals of Discrete Mathematics, Vol. 55, pp. 211-248, (1993).