Getting Started with Combinatorial Rigidity Theory

Combinatorial rigidity theory seeks to find combinatorial characterizations for infinitesimal rigidity, encoded by the Jacobian of the algebraic system of equations describing the geometric constraints. In many cases, the combinatorial properties that arise are "counting" sparsity conditions that can be determined by a simple and efficient family of algorithms called "pebble games."

Below are a few resources to get started with combinatorial rigidity theory.

Rigidity Theory

An overview can be found in this Notices of the AMS article:

Pebble Game Algorithms

Get started with this video (refer to the abstract):

pebblegame-SCG08-small.mov

Audrey Lee, Ileana Streinu, and Louis Theran. 2008. Analyzing rigidity with pebble games. In Proceedings of the twenty-fourth annual symposium on Computational geometry (SCG '08). ACM, New York, NY, USA, 226-227.

Then read the full version of pebble game algorithms for sparsity:

Audrey Lee and Ileana Streinu. Pebble game algorithms and sparse graphs, Discrete Mathematics, 308(8):1425-1437, 2008. https://arxiv.org/abs/math/0702129