Globally linked pairs of vertices in generic frameworks

A $d$-dimensional framework is a pair $(G,p)$, where $G=(V,E)$ is a graph and $p$ is a map from $V$ to ${\mathbb{R}}^d$. The length of an edge $xy\in E$ in $(G,p)$ is the distance between $p(x)$ and $p(y)$. A vertex pair $\{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 ${\mathbb{R}}^d$ when each vertex pair of $G$ is globally linked in $(G,p)$. A pair $\{u,v\}$ of vertices of $G$ is said to be weakly globally linked in $G$ in ${\mathbb{R}}^d$ if there exists a generic framework $(G,p)$ in which $\{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)$-connected graph $G$ in ${\mathbb{R}}^d$ and then show that for $d=2$ it is also necessary. We use this result to obtain a complete characterization of weakly globally linked pairs in graphs in ${\mathbb{R}}^2$, which gives rise to an algorithm for testing weak global linkedness in the plane in $O(\mathrm{\mid }V{\mathrm{\mid }}^2)$ time. Our methods lead to a new short proof for the characterization of globally rigid graphs in ${\mathbb{R}}^2$, and further results on weakly globally linked pairs and globally rigid graphs in the plane and in higher dimensions.