TR-2020-13

On the global rigidity of tensegrity graphs

Dániel Garamvölgyi



Abstract

A tensegrity graph is a graph with edges labeled as bars, cables and struts. A realization of a tensegrity graph $T$ is a pair $(T,p)$, where $p$ maps the vertices of $T$ into $\R^d$ for some $d \geq 1$. The realization is globally rigid if any realization $(T,q)$ in $\R^d$ in which the bars have the same length and the cables and struts are not longer and not shorter, respectively, is an isometric image of $(T,p)$. A tensegrity graph is weakly globally rigid in $\R^d$ if it has a generic globally rigid realization in $\R^d$, and strongly globally rigid in $\R^d$ if every generic realization in $\R^d$ is globally rigid. In this paper we give a necessary condition for weak global rigidity in $\R^d$ and prove that in the $d = 1$ case the same condition is also sufficient. In particular, our results imply that a tensegrity graph has a generic globally rigid realization in $\R^1$ if and only if it has a generic universally rigid realization in $\R^1$. We also show that recognizing strongly globally rigid tensegrity graphs in $\R^d$ is co-NP-hard for all $d \geq 1$.


Bibtex entry:

@techreport{egres-20-13,
AUTHOR = {Garamvölgyi, D{\'a}niel},
TITLE = {On the global rigidity of tensegrity graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-13}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!