Rigidity of Graphs and Frameworks: A Matroid Theoretic Approach

A d -dimensional (bar-and-joint) framework ( G, p ) consists of a graph G = ( V, E ) and a realisation p : V → R d . It is rigid if every continuous motion of the vertices which preserves the lengths of the edges is induced by an isometry of R d . The study of rigid frameworks has increased rapidly since the 1970’s, stimulated by numerous applications in areas such as civil and mechanical engineering, CAD, molecular conformation, sensor network localisation, and low rank matrix completion. We will describe some of the main results in combinatorial rigidity theory and their applications to other areas of combinatorics, putting an emphasis on links to matroid theory.