Assembly Required

What you have at hand is a special case of a very general and not theoretically unattractive mathematical problem. ...

Bill Casselman
University of British Columbia, Vancouver, Canada
Email Bill Casselman

Introduction

Well, well. The jungle gym you ordered a few weeks ago has finally arrived and, if the truth be told, it is not quite what you expected. What you are looking at after opening the package are a huge number of plastic rods, ranging greatly in size and including a few that are almost minuscule:

One thing you see immediately is that the ends of the rods all have numbers written on them. There are also a number of small gizmos at the rod ends that you don't understand. All in all, extremely puzzling! You guess that maybe you should read the Friendly Manual, so you search through the packaging material for it. You know, the packaging material you have already thrown away.

Uh, oh! There is just a single sheet with one cryptic picture and an even more cryptic sentence: "Insert gizmos in rod ends and attach rods together so that numbered ends match." The picture is this:

Then you remember that the website of the company had a picture of the gym, so you go off to look at it. What you see is this:

Well, that's clearly some help, but you would certainly like to know more. You are beginning to get a funny feeling about your new toy. It is a good idea to take a short break to think things over.

A more optimistic view

Assembling the thing seems just short of hopeless. But you start to wonder, is it really and truly hopeless? Do you in fact have enough data to do the job, even on a theoretical basis; even granting that you have enough time and energy? You start to think about the problem in a more detached manner. What you have at hand is a special case of a very general and not theoretically unattractive mathematical problem.

An object in 3D is convex if it bulges everywhere - no dimples. A doughnut is not convex, but a sphere is. A convex polytope is a convex object with a finite number of flat sides. Both of the following 3D figures are convex. (Well, at least plausibly convex, since we can only see one side.)

The picture on the left should look familiar. The skeleton of a polytope is what you get when you remove the interior of its facets. It looks as though (and is fact is it is so) your gym is the skeleton of the figure on the left. So you might wonder:

Is a convex polytope uniquely determined by its skeleton?

There are a couple of ways to interpret this, but no matter which you have in mind, the answer is "yes". However, the mathematics involved in the two cases is rather different.

In the simplest interpretation, the skeleton includes the specification, not only of its edges, but of how the edges are assembled into the facets of the object. That is to say, we specify a collection of those subsets of edges that make up the edges (or equivalently the endpoints of edges) going around a facet. In the other interpretation, all you mean by the skeleton is what data we have for the gym: a list of the edges, the numbering of the object's vertices, and a specification of how the edges connect. In other words, the second specifies much less information than the first. For example, given the collection of rods making up the gym, it is not at all obvious how to figure out how the rods determine the faces.

At any rate, if by the skeleton we mean the specification of facial structure as well, the question of uniqueness was answered in the early nineteenth century by the well-known mathematician Augustin Cauchy. This result is known as Cauchy's rigidity theorem, and Peter Cromwell's book Polyhedra is a good account. It is an old result, but nonetheless quite subtle. This is because partial assemblies of the edges, even knowing what the facets are, are not at all rigid. They can wiggle. Nonetheless, there will be basically one way to complete the assembly. (Actually two, but one is the mirror image of the other, and what you wind up with will be fixed as soon as you make an arbitrary choice of inside and outside at the start.)

The other question is perhaps more interesting. How do the connections between rods determine the facets? The main point is that there is a very simple combinatorial characterization of the facets--a combinatorial characterization as opposed to one that requires a lot of metric data. It is all about cycles.

By a cycle, I mean a sequence of vertices and edges that goes around to where it started. It may or may not be hard to find cycles in our data, but it is easy to tell whether you have one at hand. Why are we interested in cycles? First of all, the vertices of a facet and edges connecting them make up a cycle. But not just any cycle will be the boundary of a facet. Given a cycle, it is not hard to decide if it is the cycle associated with a facet. Very generally, suppose we are given a cycle of vertices $P_{0}$, $P_{1}$, $\dots$, $P_{n}$ connected by edges. Then the complement of this set of vertices will fall into two pieces, one on each side of it.

The cycle will be a facet if and only if one of these sides contains none of the vertices.

Now the partition of the vertices into sides can be decided without any geometric information, just by knowing connections: all the vertices on a side can be connected to each other by a sequence of edges on the same side. Thus to find out if we have a facet, we start with an arbitrary vertex not on the cycle and add, one after another, the vertices that can be connected to it without connecting to the cycle. If there is nothing left over when we have finished, then the cycle is a facet. Otherwise, we are in possession of a partition of the complement into two pieces, and we have reduced the difficulty of our problem because we can deal with each of the halves on its own.

This suggests a way to find the facial structure by purely combinatorial methods. (1) We find a cycle, say $C$, among the vertices. (2) We compute the partition into sides as described in the previous paragraph. (3) For each piece $V$ of vertices in one of the pieces, we make up a new structure by joining $C$ and $V$ and taking into account the connections just between $C$ and $V$. We find a cycle in this new structure that is different from $C$. Basically, we are applying the technique of "divide and conquer," and eventually we shall have in hand all the facets, specified as cycles of vertices.

For example, the magenta path is a cycle, and the complement is divided into red and pale blue nodes.

In summary, there is a simple process because it is not too difficult to find cycles; all cycles separate the remaining vertices into two (possibly empty) pieces; a cycle is the boundary of a facet if one of the two pieces is empty.

Comments?

What happens in high dimensions

This is straightforward, if a bit tedious. After all, 90 edges is a lot of edges! But in dimensions greater than three, things are much more interesting. And much, much more complicated.

In any dimension, a convex polytope determines its edge graph. The nodes are its vertices, and two vertices are linked when they are connected by an edge in the polytope. Of course there will be faces of the polytope in several dimensions, and one's immediate impression is that the edge graph cannot tell you much about the overall structure. This turns out to be true, but in a limited sense. On the one hand, it is not hard to produce polytopes with the same edge graph and different structure. There even exist polytopes of different dimension with the same edge graph. On the other, there is a very large class of interesting polytopes for which the edge graph does determine the whole thing.

A simple polytope in dimension $n$ is one whose vertices all have exactly $n$ edges meeting it. For example, the polytope on the left below is simple (even though some of the edges are very short, and from a distance might be misread) while that on the right is not.

Theorem. A simple convex polytope is uniquely determined by its edge graph.

That is to say, its facial structure is determined. This was first proved by using somewhat sophisticated and, apparently, non-constructive mathematical techniques. Then the Israeli mathematician Gil Kalai found an elementary proof, which was in some sense constructive. Only in some sense, because one could deduce from his proof an algorithm that would indeed construct the whole polytope from just the combinatorial data in its edge graph. But unfortunately it would be easy to find simple edge graphs for which it might take several human lifetimes to do this. The basic difficulty is that as before one wants to find the facets of the polytope, but that there is no easy way to tell in every case if a given subgraph of the edge graph is the boundary of a facet, much less to find candidates for this.

Hans Achatz and Peter Kleinschmidt published the first practical algorithm that recovered the facial structure from the edge graph. They published data recording how a program they had written performed, but their account of the process was virtually impossible to follow. Their algorithm has in any event been superseded by the one of Eric Friedman that I mention below, but nonetheless there would be some value in a coherent account of what they did.

One major subsequent step was in work of Michael Joswig and some colleagues, who pointed out relations with more standard problems, but the next truly significant and even unexpected step was made by Eric Friedman. He showed that the theoretical difficulty of recovering the facets from the edge graph was far less than one had expected, and by a fairly simple argument. He reduced the problem to one of a familiar type in linear programming. What is really striking in his approach is that one winds up with a problem in linear programming with a small number of variables, but a huge number of inequalities. Furthermore, at first sight it seems that it is a problem in integer programming, which are generally much more difficult than those with (say) rational solutions, but nonetheless he shows that it is equivalent to a problem in rational programming. All in all, an admirable achievement. Curiously, one of the basic tricks was introduced by Joswig et al., who showed that in order to construct the entire structure it suffices to find the faces of dimension two. Knowing these gives you enough extra information to construct the facets themselves without too much trouble.

I do not know of any accounts of Friedman's algorithms other than the original paper, nor am I aware that his algorithm has been incorporated into any general packages.

Comments?

Reading further

The literature is largely a bunch of rather short simple papers that are relatively easy to read. Nonetheless, they are not for non-technical consumption. Although there does not seem to be a recent survey, the paper by Volker Kaibel is valuable for discussion of material earlier than Friedman's breakthough.

Peter Cromwell, Polyhedra, Cambridge University Press, 1997.
Chapter 6 discusses Cauchy's rigidity theorem.
Günther Ziegler, Lectures on polytopes, Springer-Verlag, in several editions.
The reference list is thorough. Section 3.4 gives the elementary proof by Gil Kalai that in all dimensions the polytope is at least uniquely determined by its edge graph.
Eric Friedman, Finding a simple polytope from its graph in polynomial time, Discrete and combinatorial geometry 41 (2009), pages 249-256.
Altogether a very surprising discovery.
Hans Achatz and Peter Kleinschmidt, Reconstructing a simple polytope from its graph, pages 155-165 in the book Polytopes-combinatorics and computation (editors Gil Kalai and Günther Ziegler).
Volker Kaibel, Reconstructing a simple polytope from its graph, pages 281-290 in the book Combinatorial optimization (editors Jüunger, Reinelt, Renaldi).

Acknowledgement

Günther Ziegler called Eric Friedman's paper to my attention.

Bill Casselman
University of British Columbia, Vancouver, Canada
Email Bill Casselman