|
A $d$-dimensional framework is a pair $(G,p)$, where $G=(V,E)$ is a graph and $p$ is
a map from $V$ to $\RR^d$. The length of an edge $uv\in E$ in $(G,p)$ is the distance
between $p(u)$ and $p(v)$. The framework is said to be globally rigid in
$\RR^d$ if the graph $G$ and its edge lengths uniquely determine $(G,p)$, up to congruence.
A graph $G$ is called globally rigid in $\RR^d$ if every $d$-dimensional
generic framework $(G,p)$ is globally rigid.
In this paper, we consider the
problem of reconstructing a graph from the set of
edge lengths arising from a generic framework.
Roughly speaking,
a graph $G$ is strongly reconstructible in
$\CC^d$ if it is uniquely
determined by the set of (unlabeled)
edge lengths of any generic framework $(G,p)$ in $d$-space, along with the number
of its vertices. It is known
that if $G$ is globally rigid in $\RR^d$ on at least $d+2$ vertices, then it is strongly reconstructible in $\CC^d$.
We
strengthen this result and show that under the same conditions, $G$ is in fact fully reconstructible in $\CC^d$,
which means that the set of edge lengths alone is sufficient to uniquely reconstruct $G$, without any constraint on the
number of vertices.
We also
prove that if $G$ is globally rigid in $\RR^d$ on at least $d+2$ vertices, then the $d$-dimensional generic
rigidity matroid of $G$ is connected. This result generalizes Hendrickson's
necessary condition for global rigidity and
gives rise to a new combinatorial
necessary condition.
Finally, we provide new families of fully reconstructible graphs and use them to answer some questions regarding unlabeled reconstructibility posed in recent papers.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel and Gortler J., Steven and Jord{\'a}n, Tibor}, |
| TITLE | = | {Globally rigid graphs are fully reconstructible}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2021}, |
| NUMBER | = | {TR-2021-03} |