You are here

Counting on Frameworks: Mathematics to Aid the Design of Rigid Structures

Jack E. Graver
Mathematical Association of America
Publication Date: 
Number of Pages: 
Dolciani Mathematical Expositions 25
BLL Rating: 

The Basic Library List Committee recommends this book for acquisition by undergraduate mathematics libraries.

[Reviewed by
Stacy G. Langton
, on

It is plausible that the earliest mathematics was "applied" mathematics. But it seems that, once mathematical methods had been developed to solve practical problems, some of those who studied such methods were drawn irresistibly to cultivate mathematics for its own sake. Already in the Egyptian Rhind Papyrus, one of the earliest mathematical texts we have (c. 1550 B.C.), problem 40 asks how to divide 100 loaves among 5 men in such a way that the shares received are in arithmetic progression, and that one-seventh of the sum of the three largest shares is equal to the sum of the smallest two. Though this is stated as an "applied" problem, we may assume that the scribe here was just showing off his technique. So old are the "word problems" in our current textbooks.

During most of the history of mathematics, the "applied" and "pure" aspects have been closely intertwined. In our society, they have become separated — some schools even have distinct programs in "pure mathematics" and "applied mathematics".

The twentieth century was a period of great expansion and development of "pure" mathematics. It was also, however, a period in which the range of applicability of mathematics was greatly extended, and in which some branches of mathematics, such as combinatorics, which had not previously been thought of as "applied", were found to have many important applications.

Jack Graver's delightful book Counting on Frameworks, in the MAA Dolciani series, is an introduction to a new area of mathematics which has developed rapidly, starting about 1970. Inspired by practical problems, it leads to a fascinating mathematical theory — one which is still incomplete, and is being actively investigated.

The basic question goes back at least to Euler: when is a geometrical figure rigid, so that its parts cannot be moved with respect to one another? This question may be subdivided according to the kind of geometrical figures we consider. Graver's book focuses mostly on frameworks, consisting of rigid rods joined at their ends. From elementary geometry, it is clear that a framework having the shape of a triangle must be rigid. A rectangle, however, is not rigid, since it can be deformed into a parallelogram. The problem, then, is to develop criteria for rigidity.

There are two aspects to this problem: a geometric aspect and a combinatorial aspect. A geometric description of a framework will give the lengths of the bars, and specify how they are embedded in space. Since Euclidean distance is defined by a quadratic form, the condition that the bars of the framework be rigid gives a system of quadratic equations for the coordinates of the vertices. The framework will be rigid if these equations imply a unique value for the distance between any two of its vertices.

Systems of quadratic equations in several variables are difficult to work with — their study belongs to algebraic geometry. On the other hand, we might expect that, in most cases, we would not need to know the exact lengths of the bars in order to determine whether the framework was rigid or not. Thus, it would be desirable to have a purely combinatorial criterion for rigidity. A combinatorial description of the framework would simply say which pairs of vertices are spanned by a rod — in other words, it would describe the framework as a graph.

So the question is whether it is possible to give a combinatorial criterion, based on the structure of this graph, which will determine whether the corresponding framework is rigid, independently of the way in which it is actually embedded in space.

This is a difficult problem. It has been solved in dimensions 1 and 2, but is still unsolved in dimension 3. Of course, for practical applications, dimension 3 is the important case! Indeed, rigidity in dimension 1 would not seem to be particularly interesting; however, that case turns out to be the only one in which the answer is purely combinatorial; and understanding the solution in the 1-dimensional case helps in extending the theory to higher dimensions.

The result is that a 1-dimensional framework is rigid if and only if its graph is connected. Now, the theory of connected graphs is a very well-understood part of elementary combinatorics. A graph which is connected, but has as few edges as possible, is a tree. Furthermore, there is a purely combinatorial criterion on the vertices and edges of the graph which determine whether it is a tree: the number of edges must equal the number of vertices minus 1, and, in each subgraph, the number of edges can be at most the number of vertices minus 1.

A large part of Graver's book is devoted to extending this theory to the 2-dimensional case. It turns out, however, that in this case the answer cannot be purely combinatorial. There are some graphs which have particular plane embeddings whose rigidity differs from that of "typical" embeddings. The notion of a "typical" embedding is formalized in the concept of a generic embedding: the vertices of the graph must be in general position, and not have any special relationships to one another. In a certain sense, "almost all" embeddings are generic. (Those which are not generic lie in a lower-dimensional algebraic subvariety of the configuration space.)

In two dimensions, then, whether a generic embedding of a graph is rigid depends only on the combinatorial properties of the graph — and in fact the combinatorial criterion is a direct analogue of the concept of connectedness. This result was obtained by Gerard Laman in 1970. (The date "1975," given by Graver on p. 109, appears to be just a misprint.) A graph which is generically rigid in two dimensions, and which does not have any superfluous edges, is called a "2-tree", and can be characterized by a counting relationship among its vertices and edges.

An essential concept in developing this combinatorial characterization is the concept of infinitesimal rigidity. A framework is rigid if it has no deformations, while it is infinitesimally rigid if it does not even have any infinitesimal deformations. Every infinitesimally rigid framework is rigid, but there are some rigid frameworks which are not infinitesimally rigid — though they have no finite deformations, they do have infinitesimal deformations. Such frameworks are, as it were, on the very edge of being rigid. From a practical point of view, we would presumably prefer to use frameworks which are infinitesimally rigid.

Roughly speaking, we may say that the equations which define infinitesimal rigidity are obtained by differentiating the quadratic equations which define rigidity; consequently, infinitesimal rigidity is defined by a system of linear equations, which are much easier to work with. (Of course, this is a standard feature of the method of "implicit differentiation".) In particular, from linear algebra, we have the well-developed theory of the dimension of the solution space.

What about the rigidity of frameworks in three-dimensional space? By extrapolating from the 1- and 2-dimensional cases, we can write down an analogous combinatorial characterization for the 3-dimensional case. Unfortunately, simple examples are known which show that this conjectural combinatorial characterization doesn't work, and — up to now, nobody has found a combinatorial characterization which does work!

Chapter 1 of Graver's book introduces the basic ideas about rigidity in a very intuitive way. It explores the possibility of characterizing rigidity in terms of the notion of "degrees of freedom". Thus, a collection of points in 3-dimensional space has 3 degrees of freedom for each point; each rigid rod joining pairs of vertices reduces the number of degrees of freedom by 1. (Later, when the theory has been developed, the number of degrees of freedom is revealed as the linear dimension of the solution space of the system of linear equations defining infinitesimal rigidity.) This chapter also considers an important special case: a 2-dimensional rectangular grid, which can be braced by putting crossbars in some of the rectangles.

Chapter 2 develops elementary graph theory, and shows how to solve the rigidity problem for 1-dimensional frameworks. It also uses graph theory to solve the rectangular grid problem. (I used this problem as an example in a course in Combinatorics which I taught last semester, and it worked very well as a pretty application of basic graph theory.)

Chapter 3 moves up to 2-dimensional space. It introduces the concept of infinitesimal rigidity and discusses its relationship to ordinary rigidity. It gives an intuitive (though not completely rigorous) explanation of generic embeddings, and develops the combinatorial characterization of infinitesimal rigidity for graphs which are embedded generically. Finally, it considers the 3-dimensional case, and shows how the lower-dimensional approaches fail.

The final chapter contains a sketch of the history of rigidity theory, and some further applications and developments. There are sections on the theory of "linkages", such as Peaucellier's apparatus for drawing a straight line; on geodesic domes; and on "tensegrity frameworks", in which some of the rigid edges of the framework may be replaced by cables under stress.

The book is carefully written. One slip that may be confusing to the reader occurs on p. 85, where the author interchanges the sine and cosine functions in defining the polar coordinates of a point. Thus, the angle theta represents the clockwise angle which the radius vector makes with the positive y-axis. The author's subsequent discussion, however, takes for granted the conventional choice of angle.

On p. 166, in the solution of the system of 9 equations in 12 unknowns for the stresses, s13 should be -12, not -13.

It is too bad that the author was unable to present complete proofs of the fundamental results that infinitesimal rigidity implies rigidity, and that the two concepts are actually equivalent for "generic" embeddings. Unfortunately, more background in algebraic geometry and measure theory is required. The author does, however, give a careful and enlightening discussion of why these theorems should be true, with sketches of the proofs. The complete story can be found in the author's graduate-level textbook Combinatorial Rigidity.

Exercises, some of them fairly challenging, are scattered through the text. The numbering of exercises starts over in each subsection. Thus, when, on p. 124, the author refers to "Exercise 3.3", it is not immediately clear whether the reference is to the Exercise 3.3 on p. 84, to the Exercise 3.3 on p. 103, to the Exercise 3.3 on p. 114, or to the Exercise 3.3 on p. 119. (In fact, the reference is to the third of these.)

This book would be a wonderful treat for any undergraduate who knows some basic calculus and linear algebra, and who is interested in mathematics and its applications. Instead of adopting the still common "theorem-proof" format, Graver starts with a highly intuitive approach, which he pushes as far as possible, until the resulting inconsistencies and paradoxes make clear the need for a more rigorous treatment. Thus the reader who works through this material will gain some idea of how mathematical research is actually done, with its tedious calculations and dead-ends as well as its exhilarating breakthroughs. And, since the present theory is still tantalizingly incomplete in three dimensions, the reader in turn is invited to take part in the story. Perhaps the solution of the 3-dimensional case will come from readers of this book. The present book does not, however, reveal all that is known about the problem; for further results, see Combinatorial Rigidity.

One should recognize that such a "genetic" treatment has some difficulties as well as advantages. When incomplete or inadequate approaches are presented along with those that are more successful, it is easy to get confused. It is the reader's responsibility to keep track of what has been done, and to integrate the results in his own mind. In this day of watered-down textbooks which are designed to obviate any need for thought on the part of the student, perhaps the prospective reader should be forewarned.

Stacy G. Langton ( is Professor of Mathematics and Computer Science at the University of San Diego. He is particularly interested in the works of Leonhard Euler, a few of which he has translated into English.