Globally rigid graphs are fully reconstructible

Source abstract

Abstract 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 $uv\in E$ in $(G,p)$ is the distance between $p(u)$ and $p(v)$ . The framework is said to be globally rigid in $\mathbb {R}^d$ if the graph G and its edge lengths uniquely determine $(G,p)$ , up to congruence. A graph G is called globally rigid in $\mathbb {R}^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 $\mathbb {C}^d$ if the set of (unlabeled) edge lengths of any generic framework $(G,p)$ in d -space, along with the number of vertices of G , uniquely determine both G and the association between the edges of G and the set of edge lengths. It is known that if G is globally rigid in $\mathbb {R}^d$ on at least $d+2$ vertices, then it is strongly reconstructible in $\mathbb {C}^d$ . We strengthen this result and show that, under the same conditions, G is in fact fully reconstructible in $\mathbb {C}^d$ , which means that the set of edge lengths alone is sufficient to uniquely reconstruct G , without any constraint on the number of vertices (although still under the assumption that the edge lengths come from a generic realization). As a key step in our proof, we also prove that if G is globally rigid in $\mathbb {R}^d$ on at least $d+2$ vertices, then the d -dimensional generic rigidity matroid of G is connected. Finally, we provide new families of fully reconstructible graphs and use them to answer some questions regarding unlabeled reconstructibility posed in recent papers.