Title:
Combinatorial Rigidity
Authors: Jack E. Graver, Brigitte Servatius and Herman Servatius
Publisher: Graduate Studies in Math., AMS, 1993.
Card Catalog: QA 166.6.G73
Making the distinction between frameworks whose realization is rigid and those which can move is the fundamental problem of rigidity theory, which can also be considered for frameworks in higher dimensions. In low dimensions one could construct an appropriate realization of a given framework and test the model for rigidity. Of course, the mathematical task is to develop a method for predicting rigidity without building a model.
One would expect that whether a framework is rigid or not depends on both the graph (V,E) and the embedding p; or, in more general terms, that the question of rigidity has both combinatorial and geometric aspects. Our primary interest is in the combinatorial part of rigidity theory, which we call combinatorial rigidity. However, the two parts of rigidity theory are not so easily separated. In fact, only in dimensions one and two has total separation of the two parts been achieved.
In the first chapter we will give an overview of the subject, developing both aspects of the theory of rigidity informally in an historical context. This chapter stands apart from the rest of the book in that it contains no formal proofs. Most of the concepts introduced here will be reintroduced in a more formal setting later on.
The second chapter is devoted to a study of infinitesimal rigidity, a linear approximation which stands at the boundary of the combinatorial and geometric nature of rigidity. The infinitesimal approach offers at least a partial separation of the combinatorial and geometric aspects by regarding the matrix of the derivative of a framework motion as a matroid on the edges of the framework. In general, depending on the dimension and the embedding, the edges of a graph are the underlying set of several such matroids, all of which belong to the class of abstract rigidity matroids, which are defined at end of chapter 2.
The fundamental combinatorial structures used to study rigidity are the various rigidity matroids. The second chapter consists of a development of matroid theory, the theoretical foundation for much of modern combinatorics. There will of course be a special emphasis on those parts of the subject most applicable to rigidity matroids.
Chapter 3 is devoted to an extensive study of combinatorial rigidity dimension 2, which has a nice analogy, via the 1-dimensional case, with ``traditional'' graph theory from a slightly different point of view. A thorough knowledge of planar rigidity is essential to developing a good intuition for rigidity as a whole, and provides an extensive collection of tractable examples. Algorithmic and computational aspects are also treated.
In the last chapter, we discuss combinatorial rigidity in higher dimensions. Special attention is paid to dimension~3, in which there is the most practical interest, but where the characterization problem is still unsolved. Many of the results in this chapter have not yet appeared elsewhere.
The book concludes with an extensive annotated bibliography.
This text is suitable for a second graduate course in combinatorics and was already used as such at Syracuse University and at Worcester Polytechnic Institute by the authors. Each chapter contains a variety of exercises, some letting the reader fill in the details of the theory, some working through examples, as well as many which point the way to aspects of rigidity theory not covered in the text. Exercises are placed so that the reader can check his understanding of each concept before going on to the next one. The annotations in the bibliography are not only a valuable research tool, but also meant to stimulate a project oriented course of study.
Each of the chapters is mathematically self-contained, and the reader may safely peruse them in the order best suited to his background and interest.