Computing the number of realisations of a rigid graph
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911193872990208 |
|---|---|
| author | Dewar, Sean Grasegger, Georg Schicho, Josef Tewari, Ayush Kumar Warren, Audie |
| author_facet | Dewar, Sean Grasegger, Georg Schicho, Josef Tewari, Ayush Kumar Warren, Audie |
| contents | A graph is said to be rigid if, given a generic realisation of the graph as a bar-and-joint framework in the plane, there exist only finitely many other realisations of the graph with the same edge lengths modulo rotations, reflections and translations. In recent years there has been an increase of interest in determining exactly what this finite amount is, hereon known as the realisation number. Combinatorial algorithms for the realisation number were previously known for the special cases of minimally rigid and redundantly rigid graphs. In this paper we provide a combinatorial algorithm to compute the realisation number of any rigid graph, and thus solve an open problem of Jackson and Owen. We then adapt our algorithm to compute: (i) spherical realisation numbers, and (ii) the number of rank-3 PSD matrix completions of a generic partial matrix. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_02988 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Computing the number of realisations of a rigid graph Dewar, Sean Grasegger, Georg Schicho, Josef Tewari, Ayush Kumar Warren, Audie Combinatorics Algebraic Geometry Metric Geometry 52C25 (Primary) 05C10, 68R12, 14C17 (Secondary) A graph is said to be rigid if, given a generic realisation of the graph as a bar-and-joint framework in the plane, there exist only finitely many other realisations of the graph with the same edge lengths modulo rotations, reflections and translations. In recent years there has been an increase of interest in determining exactly what this finite amount is, hereon known as the realisation number. Combinatorial algorithms for the realisation number were previously known for the special cases of minimally rigid and redundantly rigid graphs. In this paper we provide a combinatorial algorithm to compute the realisation number of any rigid graph, and thus solve an open problem of Jackson and Owen. We then adapt our algorithm to compute: (i) spherical realisation numbers, and (ii) the number of rank-3 PSD matrix completions of a generic partial matrix. |
| title | Computing the number of realisations of a rigid graph |
| topic | Combinatorics Algebraic Geometry Metric Geometry 52C25 (Primary) 05C10, 68R12, 14C17 (Secondary) |
| url | https://arxiv.org/abs/2510.02988 |