Globally Linked Pairs of Vertices in Generic Frameworks

Abstract A d -dimensional framework is a pair (G, p), where G= (V, E) G = (V, E) is a graph and p is a map from V to {R}ᵈ R d. The length of an edge xy E x y ∈ E in (G, p) is the distance between p (x) and p (y). A vertex pair \u, v\ u, v of G is said to be globally linked in (G, p) if the distance between p (u) and p (v) is equal to the distance between q (u) and q (v) for every d -dimensional framework (G, q) in which the corresponding edge lengths are the same as in (G, p). We call (G, p) globally rigid in {R}ᵈ R d when each vertex pair of G is globally linked in (G, p). A pair \u, v\ u, v of vertices of G is said to be weakly globally linked in G in {R}ᵈ R d if there exists a generic framework (G, p) in which \u, v\ u, v is globally linked. In this paper we first give a sufficient condition for the weak global linkedness of a vertex pair of a (d+1) (d + 1) -connected graph G in {R}ᵈ R d and then show that for d=2 d = 2 it is also necessary. We use this result to obtain a complete characterization of weakly globally linked pairs in graphs in {R}² R 2, which gives rise to an algorithm for testing weak global linkedness in the plane in O (|V|²) O (| V | 2) time. Our methods lead to a new short proof for the characterization of globally rigid graphs in {R}² R 2, and further results on weakly globally linked pairs and globally rigid graphs in the plane and in higher dimensions.