On dimensional rigidity of bar-and-joint frameworks

Let V={1,2,…,n}V={1,2,…,n}. A mapping p:V→Rrp:V→Rr, where p1,…,pnp1,…,pn are not contained in a proper hyper-plane is called an rr-configuration  . Let G=(V,E)G=(V,E) be a simple connected graph on nn vertices. Then an rr-configuration pp together with graph GG, where adjacent vertices of GG are constrained to stay the same distance apart, is called a bar-and-joint framework (or a framework  ) in RrRr, and is denoted by G(p)G(p). In this paper we introduce the notion of dimensional rigidity of frameworks, and we study the problem of determining whether or not a given G(p)G(p) is dimensionally rigid. A given framework G(p)G(p) in RrRr is said to be dimensionally rigid iff there does not exist a framework G(q)G(q) in RsRs for s⩾r+1s⩾r+1, such that ∥qi-qj∥2=∥pi-pj∥2∥qi-qj∥2=∥pi-pj∥2 for all (i,j)∈E(i,j)∈E. We present necessary and sufficient conditions for G(p)G(p) to be dimensionally rigid, and we formulate the problem of checking the validity of these conditions as a semidefinite programming (SDP) problem. The case where the points p1,…,pnp1,…,pn of the given rr-configuration are in general position, is also investigated.