|
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:
| 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} |