On Generic Rigidity in the Plane

Let G be a graph. Let us place the points of G in “general” position in the plane and then replace its edges by rigid bars (with flexible joints). We would like to know if the resulting structure is rigid and if not, compute its “degree of freedom”. This problem was solved by Laman 6 (see also 2). In this note we give some new formulations and a new proof of Laman’s theorem, based on matroid theory, and then apply these to prove the following result: if G is 6-connected, then it will be rigid in the plane. We also construct infinitely many 5-connected graphs which do not have this property.