TR-2012-05

Strongly Rigid Tensegrity Graphs on the Line

Bill Jackson, Tibor Jordán, Csaba Király

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¹.

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 egres.elte.hu}},
INSTITUTION	=	{Egerv{\'a}ry Research Group, Budapest},
YEAR	=	{2012},
NUMBER	=	{TR-2012-05}

}