Skip to Main content Skip to Navigation
Journal articles

Lower bounds on the number of realizations of rigid graphs

Abstract : 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öbner basis computations.
Document type :
Journal articles
Complete list of metadata

Cited literature [26 references]  Display  Hide  Download

https://hal.inria.fr/hal-01711441
Contributor : Elias Tsigaridas Connect in order to contact the contributor
Submitted on : Saturday, February 17, 2018 - 9:50:34 PM
Last modification on : Wednesday, June 8, 2022 - 12:50:06 PM
Long-term archiving on: : Saturday, May 5, 2018 - 6:25:20 PM

File

lowerbounds_web.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01711441, version 1

Citation

Georg Grasegger, Christoph Koutschan, Elias Tsigaridas. Lower bounds on the number of realizations of rigid graphs. Experimental Mathematics, Taylor & Francis, In press, pp.1-22. ⟨hal-01711441⟩

Share

Metrics

Record views

133

Files downloads

115