Generic rigidity in three dimensions

Definitions and mathematical statement

For a finite simple graph $G=(V,E)$ and placement $p:V\to\mathbb R^3$, the rigidity matrix $R_3(G,p)$ has three columns per vertex and one row per edge $uv$. That row contains $p(u)-p(v)$ in the columns of $u$, $p(v)-p(u)$ in those of $v$, and zero elsewhere. Coordinates are generic when algebraically independent over $\mathbb Q$; the resulting rank is then a graph invariant.

For $n=|V|\ge3$, generic rigidity in three dimensions is equivalent to \[ \operatorname{rank}R_3(G,p)=3n-6. \] For $n\le2$, use the same geometric definition: every sufficiently nearby equivalent realization must be congruent; these small cases are directly decidable.

Can generic rigidity be recognized in deterministic polynomial time from the graph alone? Seek a combinatorial rank characterization or another deterministic method, beyond randomized evaluation of the symbolic matrix, which the source already records as available. Infinitesimal motions are vectors in the kernel of $R_3$; the allowed trivial motions come from translations and rotations. The question concerns generic placements, not accidental rank drops at special coordinates. It also differs from global rigidity: a graph may resist all local flexes while admitting a distant, noncongruent realization with exactly the same edge lengths.

Short English statement

Can one deterministically recognize generic three-dimensional rigidity in polynomial time from the graph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000038 (AMR-029-0038), 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 rigidity in three dimensions. Original source indexed by AMR-029-0038. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Generic rigidity in three dimensions. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Generic_rigidity_in_three_dimensions.