Number of Real Embeddings of Minimally Rigid Graphs

Joint work with Evangelos Bartzos, Ioannis Emiris and Elias Tsigaridas

One of the objects of interest in Rigidity Theory are the embeddings of graphs in a euclidean space $\mathbb{R}^d$ or on a sphere such that the distances between adjacent vertices satisfy given edge lengths. One of the problems is to determine the number of such embeddings modulo rigid motions.

A graph $G$ with edge lengths $\lambda$ is called rigid in $\mathbb{R}^d$ if the number of embeddings in $\mathbb{R}^d$ satisfing the constraints given by $\lambda$ is positive and finite modulo rigid motions. The graph $G$ is called generically rigid if it is rigid for $\lambda$ induced by a generic embedding. Finally, $G$ is called minimally rigid if it is generically rigid and removal of any edge yields a graph that is not generically rigid.

We are interested in finding edge lengths that can maximize the number of real embeddings of minimally rigid graphs in the plane, space, and on the sphere. To find values of the parameters that lead to graphs with a large number of real realizations, possibly attaining the upper bounds obtained by algebraic formulations, we use some standard heuristics for $\mathbb{R}^2$ and $S^2$ and we also develop a new method inspired by coupler curves for embeddings in $\mathbb{R}^3$.

Our results include the maximal numbers of real embeddings of all 7-vertex minimally rigid graphs in $\mathbb{R}^2$ and $\mathbb{R}^3$, while in the case of $S^2$ we achieve this for all 6-vertex graphs. Additionally, we increase the number of embeddings of selected bigger graphs. By gluing them together, we improve the previously known asymptotic lower bound on the maximum number of realizations among all minimally rigid graphs with a given number of vertices. The methods and the results concerning the spatial embeddings are part of the proceedings of ISSAC 2018, whereas its extension considers all cases.

Supporting material

Implementation of the method in Python: GitHub, documentation

Implementation and results for the extended paper: DOI

All supporting material for ISSAC 2018: DOI

Examples of 7 and 8-vertex minimally rigid graphs in $\mathbb{R}^3$ we studied and that are predefined in 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. Proceedings of ISSAC ‘18, 2018.

Preprint Code Dataset Project DOI


Lower bounds on the maximal number of realizations
Jun 5, 2018
On the Maximal Number of Real Embeddings of Spatial Minimally Rigid Graphs
Jul 19, 2018