Rigidity Models and Questions

Planar bar-and-joint frameworks:

A planar bar-and-joint framework is a structure made of fixed-length bars connected by universal joints, with full rotational freedom. The allowed motions are those that preserve the lengths and connectivity of the bars. (The bars are allowed to "pass through" each other.) When the only allowed motions are those that preserve the distance between every pair of joints, the framework is said to be rigid. Otherwise it is flexible.

A framework with three bars making a triangle must be rigid, since all the possible distances are fixed by bars. A rigid framework in the plane has three trivial degrees of freedom: one rotational and two translational.

On the other hand, a four-bar mechanism has a non-trivial motion, which implies that it is flexible. Since this motion is allowed even when an edge of the framework is pinned down to factor out trivial degrees of freedom, this motion is called an internal motion.

Laman's theorem and combinatorial rigidity:

The most fundamental question we can ask about a framework is whether it is rigid or flexible. For almost all planar bar-and-joint frameworks, Laman's foundational theorem gives a combinatorial answer. We associate each framework with a graph that has one vertex for each joint and one edge for each bar. (Notice that many different frameworks can have the same graph.)

Theorem (Laman):

Let G be a graph with n vertices and m edges. G is the graph of a generic minimally rigid framework if and only if: any subset of n' vertices in G spans at most 2n'-3 edge; and m=2n-3.

The genericity condition in Laman's theorem holds for almost all choices for the lengths of the bars for a given graph G. Genericity is a somewhat technical concept, but it can be intuitively thought of as playing the role of "general position" assumptions that are a paradigmatic part of computational geometry.

Rigid components and redundant edges:

Laman's theorem gives a combinatorial method for analyzing the rigidity of frameworks by counting the number of bars. For example, we can see that the triangle is minimally rigid, since 3=2×3-3 and all the subgraphs satisfy the Laman count. The four-bar mechanism must be flexible, since it 4<2×4-3=5.

Flexible frameworks still may contain substructures that move rigidly. We call a set of vertices a rigid component if it is inclusionwise maximal with the property all of the vertices in the set move rigidly with respect to each other. Since the endpoints of every bar move rigidly with respect to each other, we see that every joint much be in some rigid component. In the example of the four-bar mechanism, each bar forms one rigid component.

Rigid components of flexible frameworks need not be (and in general, will not be) single edges. In the examples above, both frameworks have one internal motion, similar to that the four-bar mechanism. However, both have a larger rigid component, highlighted in red. The example on the left, like the four-bar mechanism, does not have enough edges to be rigid.

On the right is a framework that does have enough bars to be, but it violates the Laman counts on the set of vertices shown in red. This means that there is some edge that can be removed from the framework without changing its rigidity properties. We call such an edge redundant, and such a set of vertices over constrained. Observe that there is not a single edge that is redundant in this case: removing any of the edges spanned by the highlighted set of vertices results in a framework with the same rigid components as the original. We also see here that rigid components need not be minimally rigid substructures of a framework.

Algorithmic rigidity:

Motivated by the concepts above, we define the following fundamental rigidity analysis questions.

Decision problem:

Is a framework rigid?

Extraction problem:

Find a maximum sized substructure of a framework that does not contain any redundant edges.

Components problem:

Find the rigid components of a flexible framework.

For non-generic cases, all of these questions appear to be computationally very difficult. The best known algorithms use exponential-time Gröbner basis computations, and some specific non-generic rigidity problems are known to be NP-complete.

The situation for generic rigidity is much better. The Laman counts can be verified in polynomial time by elegant and implementable pebble games, first introduced by Jacobs and Hendrickson.

Motivation:

Bar-and-joint rigidity is elegant and can be used to model many structures. However, a notable drawback (and major open problem!) is the lack of an extension of Laman's theorem to dimension 3. We now introduce another commonly used rigidity model for which there is such a theorem.

Body-bar-hinge frameworks:

A body-bar framework is a 3D structure made of rigid bodies connected by fixed-length bars attached to universal joints with full rotational freedom. (As in the case of planar bar-joint frameworks, the bodies and bars may "pass though" each other for the purpose of rigidity analysis.) A body-bar framework is rigid if the only motions which maintain the lengths of all of the bars are trivial rigid motions and flexible otherwise.

A body-bar-hinge framework is a body-bar framework that may also have hinges between two of the bodies.

The combinatorial model of a body-bar-hinge framework is a multigraph with one vertex for each body, one edge for each bar between two bodies, and five edges for each hinge between two bodies. Tay proved the following Laman like result for body-bar-hinge frameworks.

Theorem (Tay):

Let G be a graph with n vertices and m edges. G is the graph of a generic minimally rigid body-bar-hinge framework if and only if: any subset of n' vertices in G spans at most 6n'-6 edges; and m=6n-6.

We point out the similarities between the counting conditions from Tay's theorem and Laman's theorem. Intuitively, we have 6n-6 instead of 2n-3 because each rigid body has 6 trivial degrees of freedom to start with, and each bar removes at most one degree of freedom.

Bar-slider frameworks:

Our final rigidity model is an extension of 2D bar-and-joint rigidity that allows frameworks to be completely immobilized. A bar-slider is a bar-and-joint framework in which some of the joints are constrained to move on sliders which are curves that are rigidly attached to the plane. A slider functions much as a slider joint in engineering, and can be thought of as a "track".

The combinatorial model of a bar-slider framework is an extension of that for bar-joint frameworks. There is one vertex for each joint and one edge for each bar as before. Each slider is represented by a self-loop on the associated vertex.

Theorem:

Let G be a graph with n vertices m edges and k self-loops. G is the graph of a generic minimally rigid bar-slider framework if and only if:

• Any set of n' vertices spans at most 2n'-3 edges
• Any set of n' vertices spans at most 2n' edges and loops
• m+k=2n

In the context of bar-slider frameworks, rigidity is called pinning, since rigid bar-slider frameworks cannot move at all (they do not have trivial degrees of freedom).