Number of real embeddings of spatial minimally rigid graphs

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

Maple parametric search

All supporting material for ISSAC 2018: DOI

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

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



On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs
Jul 19, 2018