Rigid tensegrity labelings of graphs

Tensegrity frameworks are defined on a set of points in RdRd and consist of bars, cables, and struts, which provide upper and/or lower bounds for the distance between their endpoints. The graph of the framework, in which edges are labeled as bars, cables, and struts, is called a tensegrity graph. It is said to be rigid in RdRd if it has an infinitesimally rigid realization in RdRd as a tensegrity framework. The characterization of rigid tensegrity graphs is not known for d≥2d≥2.A related problem is how to find a rigid labeling of a graph using no bars. Our main result is an efficient combinatorial algorithm for finding a rigid cable–strut labeling of a given graph in the case when d=2d=2. The algorithm is based on a new inductive construction of redundant graphs, i.e. graphs which have a realization as a bar framework in which each bar can be deleted without increasing the degree of freedom. The labeling is constructed recursively by using labeled versions of some well-known operations on bar frameworks.