|
A $d$-dimensional framework is a pair $(G,p)$, where $G=(V,E)$ is a graph and $p$ is
a map from $V$ to $\R^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
$\R^d$ if every other $d$-dimensional framework $(G,q)$, in which
corresponding edge lengths are the same, is congruent to $(G,p)$.
In a recent paper Gortler, Theran and Thurston proved that if every generic
framework $(G,p)$ in $\R^d$ is
globally rigid for some graph $G$ on $n\geq d+2$ vertices (where $d\geq
2$), then already the set of (unlabeled) edge lengths of a generic framework
$(G,p)$, together with $n$,
determine the framework up to congruence.
In this paper we investigate the corresponding unlabeled reconstruction
problem in the case when the above generic global rigidity property does not
hold for the graph. We show families of graphs $G$ for which the set of (unlabeled)
edge lengths of every generic framework $(G,p)$ in $d$-space, along with the number
of vertices,
uniquely determine the graph, up to isomorphism. We call these graphs weakly
reconstructible. We also introduce the concept of strong reconstructibility,
which means that the bijection between the edge sets, coming from the length
condition, must be induced by a graph isomorphism.
For $d=1,2$ we give a partial (resp. complete) characterization of weak
(resp. strong) reconstructibility of graphs.
In particular, in the low-dimensional cases we describe the family of weakly
reconstructible graphs that are rigid but not redundantly rigid.
Bibtex entry:
| AUTHOR | = | {Garamvölgyi, D{\'a}niel and Jord{\'a}n, Tibor}, |
| TITLE | = | {Graph reconstruction from unlabeled edge lengths}, |
| NOTE | = | {{\tt egres.elte.hu}}, |
| INSTITUTION | = | {Egerv{\'a}ry Research Group, Budapest}, |
| YEAR | = | {2019}, |
| NUMBER | = | {TR-2019-06} |