# Lower bounds on the number of realizations of rigid graphs

arXiv: https://arxiv.org/abs/1710.08237 · HTML: https://mlsanity.com/paper/1710.08237/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Oct 2017.

## Built on by (most cited first, 1 of 1)

- [Learning Minimally Rigid Graphs with High Realization Counts](https://mlsanity.com/paper/2605.12427/) (2026)

## Abstract (arXiv)

Computing the number of realizations of a minimally rigid graph is a notoriously difficult problem. Towards this goal, for graphs that are minimally rigid in the plane, we take advantage of a recently published algorithm, which is the fastest available method, although its complexity is still exponential. Combining computational results with the theory of constructing new rigid graphs by gluing, we give a new lower bound on the maximal possible number of (complex) realizations for graphs with a given number of vertices. We extend these ideas to rigid graphs in three dimensions and we derive similar lower bounds, by exploiting data from extensive Gr"obner basis computations.