Global rigidity of (quasi)-injective frameworks on the line

Dániel Garamvölgyi


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}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2020},
NUMBER = {TR-2020-14}

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