|
A $d$-dimensional framework is a pair $(G,p)$, where $G$ is a graph and $p$ maps the vertices of $G$ to points in $\RR^d$. The edges of $G$ are mapped to the corresponding line segments. A graph $G$ is said to be globally rigid in $\RR^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 $\RR^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 $\RR^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 $\RR^d$ contain no crossing $d$-separators.
Our results give rise to new families of graphs for which global linkedness (and global rigidity) in $\RR^d$ can be tested in polynomial time.
each gluing is performed along $d$ or more vertices, then $G$ is globally rigid in $\RR^d$ if and only if it is $(d+1)$-connected.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel and Jord{\'a}n, Tibor}, |
| TITLE | = | {Partial reflections and globally linked pairs in rigid graphs}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2023}, |
| NUMBER | = | {TR-2023-05} |