Pebble games for rigidity

Checking the Laman counts:

The basic pebble game, first introduced by Jacobs and Hendrickson, is an elegant algorithm for the Decision rigidity analysis question. Press the "play" in the applet below to see it run on the triangle, which we know to be minimally rigid.

Playing the game:

The pebble game can be described in terms of its initial configuration and the allowed moves. The game is played on a directed graph (the right-hand panel in the applet), which serves as the "board".

Initial configuration:

Each vertex starts with two pebbles on it, and there are no edges.

Add edge move:

If i and j are vertices with two pebbles on each, add the edge ij (oriented toward j) and pick up one of the pebbles from i.

Pebble slide move:

If ij is an edge in the pebble game's graph and there is a pebble on j, reverse ij and move the pebble from j to i.

Edges may be added exactly when the extended graph will satisfy the Laman counts.

Theorem:

The graphs that can be constructed using the basic pebble game are exactly those that satisfy the Laman counts. The order in which the edges are added does not matter.

To use the pebble game for the Decision problem the strategy is then to try and collect four pebbles on the ends of each of the inputs edges in an arbitrary order. Since the pebbles can be collected with DFS, this algorithm is polynomial time.

Rejecting redundant edges:

When there are redundant edges in the input, it is impossible to collect the four pebbles required to add the edge. Observe in the example below that once there are 5 edges spanned by the bottom vertices, it is impossible to collect four pebbles one the edges of the sixth edge in this subgraph, so the edge is rejected.

Finding and maintaining rigid components:

We extended the pebble game to find and update the rigid components of the pebble game graph each time an edge is added. In the example below, each rigid component is shown in a different color on the right.

The components pebble game solves the Components rigidity question. Maintaing components, with an appropriate data structure we call union/pair-find also allows redundant edges to be rejected in constant time. This improves the O(n³) running time of the basic pebble game on dense inputs to O(n²).

The pebble game for Tay's counts:

Our pebble game for body-bar rigidity has a similar structure to the pebble game for 2D baj-and-joint rigidity. We describe it in terms of the initial configuration and the allowed moves, showing the differences in bold.

Initial configuration:

Each vertex starts with six pebbles on it, and there are no edges.

Add edge move:

If i and j are vertices with at least seven pebbles between them, add the edge ij (oriented toward j) and pick up one of the pebbles from i.

Pebble slide move:

If ij is an edge in the pebble game's graph and there is a pebble on j, reverse ij and move the pebble from j to i.

We see that the rules for moving pebbles are the same, and that the different counts are captured by the number of pebbles that start on each vertex and the number of pebbles required to add an edge.

All the variants of the pebble game work with the 6n-6 counts. Here we show the components pebble game for body-bar.

Note that in body-bar rigidity, not every vertex and edge needs to be in a rigid component. This example is minimally rigid, but has no rigid components if any of the edges are removed. Observe that as the game is being played, none of the edges on the right are colored (to indicate that they are in a component) until the last step.

Checking the bar-slider counts:

Recall that for bar-slider rigidity, there are two counting conditions to check: the Laman counts for subgraphs containing only edges; and 2n' counts for subgraphs containing edges and loops.

The pebble game for bar-slider rigidity uses a "two level" strategy. First it verifies that a new edge or loop satisfies the less stringent 2n'; then it temporarily replaces all the previously accept loops with edge and uses the Laman rigidity pebble game to check the 2n'-3 counts for edges. If both tests pass, then the new edge is accepted.

The red and blue colors of the edges in the right panel show a tree decomposition of the graph that has a rigidity-theoretic interpretation.