Sufficient conditions for the global rigidity of graphs

Abstract

We investigate how to find generic and globally rigid realizations of graphs in R(d) based on elementary geometric observations. Our arguments lead to new proofs of a combinatorial characterization of the global rigidity of graphs in R(2) by Jackson and JoRdán and that of body-bar graphs in R(d) recently shown by Connelly, JoRdán, and Whiteley. We also extend the 1-extension theorem and Connelly's composition theorem, which are main tools for generating globally rigid graphs in R(d). In particular we show that any vertex-redundantly rigid graph in R(d) is globally rigid in R(d), where a graph G=(V, E) is called vertex-redundantly rigid if G−v is rigid for any v∈V.