Characterizing globally linked pairs in graphs

Abstract

A pair $\{u,v\}$ of vertices is said to be globally linked in a $d$-dimensional framework $(G,p)$ if there exists no other framework $(G,q)$ with the same edge lengths, in which the distance between the points corresponding to $u$ and $v$ is different from that in $(G,p)$. We say that $\{u,v\}$ is globally linked in $G$ in ${\mathbb{R}}^d$ if $\{u,v\}$ is globally linked in every generic $d$-dimensional framework $(G,p)$. We give a complete combinatorial characterization of globally linked vertex pairs in graphs in ${\mathbb{R}}^2$, solving a conjecture of Jackson, Jordán and Szabadka from 2006 in the affirmative. Our result provides a refinement of the characterization of globally rigid graphs in ${\mathbb{R}}^2$ as well as an efficient algorithm for finding the globally linked pairs in a graph. We can also deduce that globally linked pairs in ${\mathbb{R}}^2$, globally linked pairs in ${\mathbb{C}}^2$, and stress-linked pairs in ${\mathbb{R}}^2$ are all the same, settling conjectures of Jackson and Owen, and Garamvölgyi, respectively. In higher dimensions we determine the globally linked pairs in body-bar graphs in ${\mathbb{R}}^d$, for all $d\ge 1$, verifying a conjecture of Connelly, Jordán and Whiteley.