Nets: A Tool for Representing Polyhedra in Two Dimensions **Nets: A Tool for Representing Polyhedra in Two Dimensions**

**Feature Column Archive**

We live in a 3-dimensional (3D) world but we constantly want to represent what we see in 3D in two dimensions (2D), specifically a plane. We have a lot of practice reconstructing 3D objects from our experiences with TV screens, magazines, photographs, and paintings. However, not only do we incidentally learn to deal with how 2D represents 3D, but many professions train people to make such representations accurate. Thus, architects and home decorators draw sketches of buildings they design for clients or the layout of a room for your dream home.

Artistic attempts to depict 3D in 2D are as old as the caves in Lascaux, the tombs in Egypt, and walls of the villas in Pompeii and as new as Andy Warhol's canvasses. However, many of the ancient depictions of 3D in 2D are nifty but stylized, as, for example, the way of drawing people in ancient Egyptian art. By the Renaissance professional artists were consciously trying to find ways to make realistic looking representations in 2D of what the eye saw in 3D. Does it surprise you that many of these pioneer artists (Brunelleschi, Alberti, Veneziano, Piero della Francesca, etc.) were involved with mathematics as well as art? Perhaps not, for mathematicians are no less concerned with patterns than artists. What was the challenge that these artists faced?

Clearly 2D is not 3D, so in a broad sense a 3D object must be distorted or transformed to turn it into something 2D. The goal, of course, is that we recognize what the object is from its representation, so the transformed version can not be too different in some ways from the original. This suggests thinking about representing an object in 2D from 3D in terms of the properties that must be given up and those properties that the artist wishes to preserve. If the 3D object is red, there is no reason we can not make our 2D object red, so we do not have to give up color. However, what potentially might have to go?

The Renaissance artists were very sensitive to the issue of what aspects of the original object they wanted to be preserved in the paintings they made. In representing box shaped buildings, the originators of the use of parallel projection and perspective were willing to sacrifice some geometrical information about the original box in order to preserve some other information. For example, one might be willing to distort length, parallelism of lines, angle size, or preservation of area.

However, suppose that one wants to preserve the lengths of lines and angles in the representation of the polygons that make up a building. For simplicity we will assume that buildings are convex polyhedra. Is such a representation possible?

The surprising answer is a resounding, "We are not sure!" Perhaps it will also surprise you that one of the early pioneers of developing such a representation was the mathematically inclined artist Albrecht Dürer (1471-1528). To understand the situation fully, let us explore further.

Consider a simple example of the kind of thing I mean. Perhaps the most familiar of 3-dimensional convex polyhedra is the cube. The cube can be thought of as a certain combinatorial object, where attention is paid to how its pieces fit together, along with additional geometrical information that involves distances and angles (so called metrical information). Thus, combinatorially, one can think of the cube as a convex polyhedron which has 8 vertices, 12 edges, and 6 faces, where each face is a polygon consisting of 4 sides. A 3-dimensional solid that obeys these conditions I will call a combinatorial cube. Can you visualize the kind of object I am describing?

If you are having trouble visualizing the combinatorial cube, there is a simple way to do this using a geometrical diagram called a graph. A graph is a geometrical tool which involves a collection of points called vertices joined by line segments called edges. The figure below shows some examples of graphs which have been drawn in a plane. In the diagram shown only the small circles represent vertices. If lines cross at points other than vertices, then these crossings are not vertices of the graph.

However, not all of these diagrams can correspond to the graph (sometimes called the 1-skeleton) of the vertices and edges of 3-dimensional polyhedra. Can you identify which one can represent a polyhedron? None of them represents a cube. Below is a whole group of graphs which are each structurally like a cube, and, thus, represent combinatorial cubes.

Can you locate in each of these diagrams the 8 vertices, 12 edges, and 6 four-sided regions that correspond to the 6 4-sided polygons? The top right diagram is especially clear because the edges meet only at vertices. Notice that although you probably recognized the top left diagram as a cube because cubes are often shown this way, there are two pairs of edges of the combinatorial cube which meet at points which are not vertices of the graph. The edges shown crossing in the 2D version do not cross in 3D.

There are, in fact, a lot of things that are familiar to you that have this shape: a cereal box, a box-like skyscraper, or a square pyramid with its top cut off parallel to the base! To this combinatorial information we can add geometric information. One way to add geometric information would be to add information about the lengths of the sides of the polygons. If we say that edges that make up the polyhedron all have length 1, then we certainly can not be thinking about a truncated pyramid, but it is not yet the solid that is called a cube. Can you visualize a combinatorial cube which is not a cube but where all the edges have the same length? (Note: there are ways to measure lengths of distances between points in 3-dimensional space other than Euclidean distance so when I mention length, I should make clear, as I mean here, that I am talking about Euclidean distance.) The reason is that what has just been described might have all its faces consisting of rhombuses which are not squares. Can you visualize a combinatorial cube all of whose faces are rhombuses such as the one below?

However, think about the combinatorial cube endowed with all the faces being squares. In this case it is possible to cut along the edges of the cube to release the polygonal faces that make up the cube, thereby drawing a 2D representation with lengths and angles in the faces preserved.

Can you visualize the polygon that results from unfolding and flattening out the polygonal faces that make up a cube when the cuts along the dark edges shown below are made?

A polygonal region which can be folded up to form a polyhedron is usually called a net of the polyhedron, and some polyhedra have many nets, in the sense that very different looking polygons will fold to the same 3-dimensional polyhedron. Can you verify that there are 11 different nets for the cube?

In attempting to open a polyhedron by cutting along its edges so as to be able to flatten it out and open it up into a polygon, one can not choose any edges one wants. Clearly if one cuts along all the edges that surround a face, that face will separate from the rest of the polygons, which is something one wants to avoid. Furthermore, if one does not cut at least one edge at a vertex, one will not be able to release the polygons at that vertex. This means that the edges that one cuts consist of a special kind of graph called a spanning tree of the graph of the polyhedron. A tree is a connected graph which has no circuit. A spanning tree of a graph is a subgraph of the original that includes all the vertices of the original.

Some experiments should convince you that many of the polyhedra you are most familiar with such as the regular tetrahedron, the regular octahedron, a square based pyramid, or a triangular prism have nets; in fact, they have several different ones.

The edges of a convex polyhedron which are not part of the spanning tree that one cuts in attempting to produce a net wind up as the lines to fold along in folding the net back up to form the original polyhedron. Can you see how to fold the polygon below (internal diagonals shown) into a cube?

The word net of a polyhedron is not defined everywhere in exactly the same way. We will see some problems with the definition as given above shortly. Note that not every diagram that looks like a net is a net! An example is shown in the diagram below. What goes wrong when you try to fold this diagram into a polyhedron?

However, I am sure that you can convince yourself that a 1x1x2 brick (which is a combinatorial cube) has many nets. The next problem is that the definition that we gave for net is not as well defined as it might seem from the examples of nets one might try, based on ideas about familiar polyhedra such as a regular tetrahedron, a square pyramid, or a triangular prism (whose faces are equilateral triangles and squares).

What polyhedron results if you fold the polygon shown below?

You may be surprised to learn that there is not a unique answer to this question! There are two different ways to fold the polygon shown. One way yields the convex 3-dimensional solid known as the (regular) octahedron. The other solid is non-convex and also consists of eight triangles, so it is an octahedron, too.

Below, the earlier polygon is redrawn showing the different gluing instructions for the edges along the boundary which give rise to two different polyhedra.

Unfortunately, when one cuts along some spanning trees of the vertex-graph of a 3-dimensional convex polyhedron, sometimes the result has its polygonal faces overlap. This can occur for surprisingly simple polyhedra, even for (non-regular) tetrahedra! There is an example due to M. Namiki that illustrates this phenomenon.

This raises the natural question of whether or not for any convex 3-dimensional polyhedra there is a spanning tree that one can cut along which will open the polyhedron so that it can be unfolded and flattened out without the polygons making up the polyhedron overlapping. In other words does every convex 3-dimensional polyhedron have a net? This question, which seems to have been first raised by the British mathematician G. C. Shephard in 1975, is still unsolved! Perhaps some reader can provide a proof or a counterexample. (This would require find a convex polyhedron such that cutting along every spanning tree would yield an overlapping unfolding.)

A variety of efforts to resolve and get deeper insight into nets for polyhedra has been undertaken. One approach was that of Catherine Schevon, a doctoral student of Joseph O'Rourke (then in the Computer Science Department at Johns Hopkins and now in the Computer Science Department at Smith College). Her work related to finding a way of generating random 3-dimensional convex polyhedra and then choosing a random unfolding (not such simple issues) and seeing if the random unfolding overlapped. Her results showed that as the number of vertices of the solid increased, for a fixed specific solid the number of unfoldings where an overlap did occur increased. She conjectured that as the number of vertices of a 3-dimensional polytope goes to infinity, the probability of a random unfolding of a random polytope overlapping approaches one. However, in all the cases that were studied it was possible to find an unfolding.

A different tack was taken by Wolfram Schlickenrieder, a doctoral student of Günther Ziegler. Schlickenrieder's idea was to try to find a type of spanning tree that always seemed to lead to an unfolding without overlaps, and then to see if a rigorous proof that this type of tree would always work could be found. Unfortunately, what happened was that no matter what reasonable type of tree Schlickenrieder picked, he was able to find examples of 3-dimensional convex solids where this tree did not lead to a net unfolding without overlaps. Among the types of trees he considered were: breadth-first search tree, depth-first search tree, shortest paths tree, and a variety of others.

Other investigators have called attention to ideas related to Shephard's Conjecture:

1. Suppose that one considers cuts other than along edges of the polyhedron. Work by Boris Aronov and Joseph O'Rourke has showed that every convex 3-dimensional polyhedron has a star unfolding, which is a way of unfolding a polyhedron by cutting along shortest paths (on the surface) of it.

2. Shephard's conjecture is false for non-convex 3-dimensional polyhedra. This work is due to M. Bern, E. Demaine, D. Eppstein, and E. Kuo.

3. Alexandrov's Theorem addresses conditions under which a polygon will fold into a convex polyhedron.

In the references section you will find additional avenues to pursue, as well as places where this topic is treated on the Web.

As regards Shephard's Conjecture, my guess is that it is true.

*Joseph Malkevitch*

York College (CUNY)

* Email: malkevitch@york.cuny.edu*