Generic global rigidity in three dimensions

Definitions and mathematical statement

Let $G=(V,E)$ be a finite simple graph. A placement $p:V\to\mathbb R^3$ is generic when all its coordinates are algebraically independent over $\mathbb Q$. Two placements $p,q$ are equivalent if \[ \|p(u)-p(v)\|=\|q(u)-q(v)\| \quad(uv\in E), \] and congruent if this equality holds for every pair of vertices. Generic global rigidity means that every placement equivalent to a generic one is congruent to it. This property depends only on $G$.

The problem is to recognize generically globally rigid graphs in three-dimensional space by a deterministic polynomial-time algorithm or an effective combinatorial characterization. The input consists of vertices and edges, not a framework given with possibly exceptional coordinates.

The source notes an algebraic characterization giving randomized polynomial-time recognition. The remaining target is therefore not bare decidability or the existence of a probabilistic test. Nor is it enough to test local rigidity, which excludes a continuous flex but can allow isolated noncongruent equivalent frameworks. Congruence allows reflections as well as rotations and translations; orientation of the ambient space is not fixed. Small complete graphs satisfy the definition without any full-dimensional assumption on their affine spans, so those cases can be handled directly.

Short English statement

Find deterministic or combinatorial recognition of graphs whose generic three-dimensional realizations are uniquely determined by their edge lengths.

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000037 (AMR-029-0037), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Generic global rigidity in three dimensions. Original source indexed by AMR-029-0037. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Generic global rigidity in three dimensions. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Generic_global_rigidity_in_three_dimensions.