|Audrey St. John||
RigidityI 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 rigidityConsider 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
3D body-and-bar/hinge rigidityConsider 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.
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:
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.
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.