Directions in graph rigidity
Given a graph G and an embedding of its vertices in R^d, what continuous motions of the vertices preserve all edge lengths?
Clearly all motions induced by an isometry of R^d do, these are the trivial motions; are there any others?
If the answer is NO for all (equivalently, for one) generic embedding, G is called d-rigid. What are the d-rigid graphs?
This problem has been extensively studied since the 70s, and is still widely open for d>=3.
It is studied mainly from algebraic geometry, linear algebra, and combinatorics points of view.
Variants of it, especially in dimensions 2 and 3, are of importance also beyond mathematics, e.g. in structural engineering, computational biology and more.
I will discuss various directions and open problems in graph rigidity, including:
combinatorial characterization, numerical consequences, non-generic rigid embeddings, rigidity of random graphs,
and a quantitative version of rigidity via spectral analysis of the related stiffness matrix.
Last Updated Date : 11/05/2022