A Review of the Notion of Graph Rigidity and Some Recent Developments

A d-dimensional framework is a pair (G,p⃗ ) consisting of a finite simple graph G and an embedding p⃗  of its vertices in ℝd. A framework is called rigid if every continuous motion of the vertices in ℝd that starts at p⃗ , and preserves the lengths of all the edges of G, does not change the distance between any two vertices of G. In general, determining whether a framework is rigid is a hard problem that may depend on the particular embedding. However, if the embedding is generic, rigidity depends only on the underlying graph.

In the first half of the talk I will review the definitions and some basic properties of rigid graphs, and tell about some new sufficient (combinatorial) conditions for a graph to be rigid in ℝd. In the second half, I will tell about some connections of this notion to Erdős-type problems in combinatorial geometry.