Globally Linked Pairs of Vertices in Generic Frameworks

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 ,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 ,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 ,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.