TR-2019-06

Graph reconstruction from unlabeled edge lengths

Dániel Garamvölgyi, Tibor Jordán



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 $\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:

@techreport{egres-19-06,
AUTHOR = {Garamvölgyi, D{\'a}niel and Jord{\'a}n, Tibor},
TITLE = {Graph reconstruction from unlabeled edge lengths},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2019},
NUMBER = {TR-2019-06}
}


Last modification: 29.12.2020. Please email your comments to Tamás Király!