|
A realization of a graph $G$ is a pair $(G,p)$ where $p$ maps the vertices of $G$ into Euclidean space $\R^d$. The realization is injective if $p$ is injective and quasi-injective if for each edge of $G$, $p$ maps the endpoints of the edge to different points in space. The realization is globally rigid if any realization $(G,q)$ in $\R^d$ with the same edge lengths is congruent to $(G,p)$.
In this paper we characterize graphs that have an injective (quasi-injective, respectively) non-globally rigid realization in $\R^1$, and we show that the problem of recognizing these graphs is NP-complete in both the injective and the quasi-injective cases. Our characterizations are based on the notion of NAC-colorings, which have been used previously to investigate similar problems in the plane. We also give an overview of related results and open problems in rigidity theory.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel}, |
| TITLE | = | {Global rigidity of (quasi)-injective frameworks on the line}, |
| NOTE | = | {{\tt www.cs.elte.hu/egres}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2020}, |
| NUMBER | = | {TR-2020-14} |