Audrey St. John


I am interested in problems relating to the rigidity of geometric constraint systems. We motivate the concepts in rigidity theory by starting with the most well-studied model of 2D bar-and-joint. Note that, while an elegant combinatorial characterization exists for 2D, such a characterization for 3D bar-and-joint rigidity remains one of the biggest open problems in rigidity theory! What is known about 3D is a result for a different type of model, called body-and-bar structures.

Coming soon -- more definitions and examples, including pinning (via sliders) and directional ("parallel redrawings") rigidity!

2D bar-and-joint rigidity

Consider a structure composed of universal joints connected by fixed-length bars in the plane. Such a structure may be rigid or flexible:

For example, a triangle is rigid once its edge lengths are fixed; the only motion in the plane that would maintain the distance constraints are trivial motions (translation and rotation). On the other hand, a four-bar structure is flexible and admits a non-trivial motion; we say such a structure has one "internal degree of freedom." When counting "degrees of freedom," the trivial degrees are often taken into account, meaning that the triangle would have 3 degrees of freedom, whereas the four-bar structure has 4. To gain more intuitions as to how bar-and-joint structures in the plane move, try the 2D motion simulation demo.

So-called "generic" rigidity for 2D bar-and-joint structures was characterized by Laman in 1970 with a counting property, stated as follows:

Theorem [Laman, 19070]: A graph with n vertices and m edges is (generically) minimally rigid if and only if
  • m = 2n - 3
  • for all subsets of n' vertices, m' <= 2n' - 3, where m' is the number of edges spanned by that vertex set
This characterization of generic 2D bar-and-joint rigidity was later used by Hendrickson in his thesis as the basis for the elegant 2D pebble game, introduced by Jacobs and Hendrickson in 1997.

3D body-and-bar/hinge rigidity

Consider a structure composed of rigid bodies in 3-space, connected by fixed-length bars and hinges. A bar is rigidly attached at its endpoints to the bodies by universal joints, imposing a distance constraint. A hinge is shared among two bodies and imposes both a distance and an angle constraint; the only motion allowed is rotation about the hinge axis.
Example 1 of a body-and-bar/hinge structure Example 2 of a body-and-bar/hinge structure

Both Examples 1 and 2 above are minimally rigid structures, but how can we tell? In 1984, Tay characterized minimally (generically) rigid body-and-bar structures as follows:

Theorem[Tay, 1984]: Given a 3D body-and-bar structure, associate a graph by mapping bodies to vertices and bars to edges. The original structure is rigid if and only if the associated graph is the edge-disjoint union of 6 spanning trees.

Tay's Theorem also applies to body-and-hinge and body-and-bar/hinge structures, given the observation that a hinge is equivalent to 5 bars [Tay, Whiteley].

A famous result of Nash-Williams and Tutte (independently) characterizes those graphs that are the edge-disjoint union of k spanning trees with a counting property:

Theorem[Nash-Williams, Tutte]: A graph with m edges and n vertices is the edge-disjoint union of k spanning trees if and only if:
  • m = kn-k
  • for all subsets of n' vertices, m' <= kn'-k, where m' is the number of edges spanned by the vertex set
Note that this characterization is equivalent to the (k, k)-tightness property.

For instance, here we see the two graphs associated with Examples 1 and 2; note that the graph for Example 1 is colored to see 6 edge-disjoint spanning trees. Both examples satisfy the counting property of (6,6)-tightness.
Associated graph for Example 1 Associated graph for Example 2

Because Tay's result relates 3D body-and-bar/hinge rigidity to (6,6)-tight graphs, the (6,6)-pebble game can be used for solving (generic) rigidity problems in this model.