TOPICS
Search

Fully Reconstructible Graph

A graph G is fully reconstructible in C^d if the graph is determined from its d-dimensional measurement variety. If G is globally rigid in R^d on n>=d+2 vertices, then G is fully reconstructible in C^d (Garamvölgyi et al. 2021). The full reconstructibility problem has been solved for d=1 and d=2 (Bernstein and Gortler 2022).

For G a graph on three or more vertices with no isolated vertices, G is fully reconstructible in C^1 iff it is 3-connected (Garamvölgyi et al. 2021, Bernstein and Gortler 2022).

For G a graph on four or more vertices, G is fully reconstructible in C^2 iff G is generically globally rigid in two dimensions (Garamvölgyi et al. 2021, Bernstein and Gortler 2022).

The disposition of full reconstructibility of graphs in d=3 is not fully determined, although some necessary and some sufficient conditions are known. Bernstein and Gortler (2022) showed that the complete bipartite graph K_(5,5) is fully reconstructible in C^3.

See also

Generically Globally Rigid

Explore with Wolfram|Alpha

References

Bernstein, D. I. and Gortler, S. J. "K_(5,5) is Fully Reconstructible in C^3." Submitted to Disc. Math., 2022.Garamvölgyi, D.; Gortler, S. J.; and Jordán, J. "Globally Rigid Graphs Are Fully Reconstructible." 10 May 2021. https://arxiv.org/abs/2105.04363.

Cite this as:

Weisstein, Eric W. "Fully Reconstructible Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/FullyReconstructibleGraph.html

Subject classifications