Partial reflections and globally linked pairs in rigid graphs

Abstract

A $d$-dimensional framework is a pair $(G,p)$, where $G$ is a graph and $p$ maps the vertices of $G$ to points in ${\mathbb{R}}^d$. The edges of $G$ are mapped to the corresponding line segments. A graph $G$ is said to be globally rigid in ${\mathbb{R}}^d$ if every generic $d$-dimensional framework $(G,p)$ is determined, up to congruence, by its edge lengths. A finer property is global linkedness: we say that a vertex pair $\{u,v\}$ of $G$ is globally linked in $G$ in ${\mathbb{R}}^d$ if in every generic $d$-dimensional framework $(G,p)$ the distance of $u$ and $v$ is uniquely determined by the edge lengths. In this paper we investigate globally linked pairs in graphs in ${\mathbb{R}}^d$. We give several characterizations of those rigid graphs $G$ in which a pair $\{u,v\}$ is globally linked if and only if there exist $d+1$ internally disjoint paths from $u$ to $v$ in $G$. We call these graphs $d$-joined. Among others, we show that $G$ is $d$-joined if and only if for each pair of generic frameworks of $G$ with the same edge lengths, one can be obtained from the other by a sequence of partial reflections along hyperplanes determined by $d$-separators of $G$. We also show that the family of $d$-joined graphs is closed under edge addition, as well as under gluing along $d$ or more vertices. As a key ingredient to our main results, we prove that rigid graphs in ${\mathbb{R}}^d$ contain no crossing $d$-separators. Our results give rise to new families of graphs for which global linkedness (and global rigidity) in ${\mathbb{R}}^d$ can be tested in polynomial time.