Globally linked pairs of vertices in rigid frameworks

Bill Jackson, Tibor Jordán, Zoltán Szabadka

Published in:
Rigidity and Symmetry (R. Connelly, W. Whiteley and Asia Weiss, eds.), Fields Institute Communications, in press.


A 2-dimensional framework $(G,p)$ is a graph $G=(V,E)$ together with a map $p:V\to {\mathbb{R}}^2$. We consider the framework to be a straight line realization of $G$ in $\mathbb{R}^2$. Two realizations of $G$ are equivalent if the corresponding edges in the two frameworks have the same length. A pair of vertices $\{u,v\}$ 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 different.

Bibtex entry:

AUTHOR = {Jackson, Bill and Jord{\'a}n, Tibor and Szabadka, Zolt{\'a}n},
TITLE = {Globally linked pairs of vertices in rigid frameworks},
NOTE= {{\tt}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-19}

Last modification: 29.12.2020. Please email your comments to Tamás Király!