Rigid tensegrity labelings of graphs

AbstractTensegrity frameworks are defined on a set of points in Rd 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 Rd if it has an infinitesimally rigid realization in Rd as a tensegrity framework. The characterization of rigid tensegrity graphs is not known for d≥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=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