Published in:
Discrete Applied Mathematics 161:(7-8) pp. 1147-1149. (2013)
Tensegrity frameworks are defined on a set of points in R^{d} 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 strongly rigid in R^{d} if every generic realization in R^{d} as a tensegrity framework is infinitesimally rigid. In this note we show that it is NP-hard to test whether a given tensegrity graph is strongly rigid in R^{1}.
Bibtex entry:
@techreport{egres-12-05,
AUTHOR | = | {Jackson, Bill and Jord{\'a}n, Tibor and Kir{\'a}ly, Csaba}, |
TITLE | = | {Strongly Rigid Tensegrity Graphs on the Line}, |
NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
YEAR | = | {2012}, |
NUMBER | = | {TR-2012-05} |