Computer Science/Discrete Mathematics Seminar II
A Review of the Notion of Graph Rigidity and Some Recent Developments
A d-dimensional framework is a pair $(G, \vec{p})$ consisting of a finite simple graph $G$ and an embedding $\vec{p}$ of its vertices in $\mathbb{R}^d$. A framework is called rigid if every continuous motion of the vertices in ${\mathbb R}^d$ that starts at $\vec{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 $\mathbb{R}^d$. In the second half, I will tell about some connections of this notion to Erdős-type problems in combinatorial geometry.