|
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 $\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 $\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 $\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 $\R^2$, which gives rise to an algorithm for testing weak global linkedness in the
plane in $O(|V|^2)$
time. Our methods lead to
a new short proof for the characterization of globally rigid graphs in $\R^2$, and further
results on weakly globally linked pairs and globally rigid graphs in the plane and in higher
dimensions.
Bibtex entry:
| AUTHOR | = | {Jord{\'a}n, Tibor and Vill{\'a}nyi, Soma}, |
| TITLE | = | {Globally linked pairs of vertices in generic frameworks}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2023}, |
| NUMBER | = | {TR-2023-07} |