*Joint work with Evangelos Bartzos, Ioannis Emiris and Elias Tsigaridas*

The number of embeddings of minimally rigid graphs in $\mathbb{R}^d$ is (by definition) finite, modulo rigid transformations, for every generic choice of edge lengths. Even though various approaches have been proposed to study it, the gap between upper and lower bounds is still enormous. Precise estimations and its asymptotic behavior are still major and fascinating open problems in theory of rigid graphs.

Our work considers the maximal number of real embeddings of
minimally rigid graphs in $\mathbb{R}^3$ (Geiringer graphs). We modify a commonly used
parametric semi-algebraic formulation that exploits the
Cayley-Menger determinants
to minimize the *a priori* number of complex embeddings, where the
parameters correspond to edge lengths. To cope
with the huge dimension of the parameter space and find specializations of
the parameters that maximize the number of real embeddings, we
introduce a method based on coupler curves
that makes the sampling feasible for spatial minimally rigid
graphs.

Our methodology results to the first full classification of the number of real embeddings of graphs with 7 vertices in $\mathbb{R}^3$, which was the smallest open case. Building on this, we improve the previously known general lower bound on the maximum number of real embeddings in $\mathbb{R}^3$.

For bibliograpy and description of the method, see the ISSAC’18 paper On the maximal number of real embeddings of spatial minimally rigid graphs.

## Supporting material

Implementation of the method in Python: GitHub, ISSAC’18 version

Construction of Geiringer graphs

Computation of mixed volume and complex solutions

All supporting material for ISSAC 2018:

7 and 8-vertex graphs we studied and that are supported by the Python code:

Screenshot of the program plotting a coupler curve of $G_{48}$: