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

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 pis 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. (C) 2021 The Author(s). Published by Elsevier B.V.