on Combinatorial Optimization Technical reportS

A 2-dimensional framework (G; p) is a graph G = (V;E) together with a map p: V! R2. We consider the framework to be a straight line realization of G in R2. Two realizations of G are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices fu; vg is globally linked in G if the distance between the points corresponding to u and v is the same in all pairs of equivalent generic realizations of G. In this paper we extend our previous results on globally linked pairs and complete the characterization of globally linked pairs in minimally rigid graphs. We also show that the Henneberg 1-extension operation on a non-redundant edge preserves the property of being not globally linked, which can be used to identify globally linked pairs in broader families of graphs. We prove that if (G; p) is generic then the set of globally linked pairs does not change if we perturb the coordinates slightly. Finally, we investigate when we can choose a non-redundant edge e of G and then continuously deform a generic realization of G e to obtain equivalent generic realizations of G in which the distances between a given pair of vertices are dierent.