Learning Minimally Rigid Graphs with High Realization Counts
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914559819776000 |
|---|---|
| author | Slyvka, Oleksandr Rubeš, Jan Alves, Rodrigo Legerský, Jan |
| author_facet | Slyvka, Oleksandr Rubeš, Jan Alves, Rodrigo Legerský, Jan |
| contents | For minimally rigid graphs, the same edge-length data can admit multiple realizations (up to translations and rotations). Finding graphs with exceptionally many realizations is an extremal problem in rigidity theory, but exhaustive search quickly becomes infeasible due to the super-exponential growth of the number of candidate graphs and the high cost of realization-count evaluation. We propose a reinforcement-learning approach that constructs minimally rigid graphs via 0- and 1-extensions, also known as Henneberg moves. We optimize realization-count invariants using the Deep Cross-Entropy Method with a policy parameterized by a Graph Isomorphism Network encoder and a permutation-equivariant extension-level action head. Empirically, our method matches the known optima for planar realization counts and improves the best known bounds for spherical realization counts, yielding new record graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_12427 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Learning Minimally Rigid Graphs with High Realization Counts Slyvka, Oleksandr Rubeš, Jan Alves, Rodrigo Legerský, Jan Machine Learning Combinatorics 52C25, 68R12 For minimally rigid graphs, the same edge-length data can admit multiple realizations (up to translations and rotations). Finding graphs with exceptionally many realizations is an extremal problem in rigidity theory, but exhaustive search quickly becomes infeasible due to the super-exponential growth of the number of candidate graphs and the high cost of realization-count evaluation. We propose a reinforcement-learning approach that constructs minimally rigid graphs via 0- and 1-extensions, also known as Henneberg moves. We optimize realization-count invariants using the Deep Cross-Entropy Method with a policy parameterized by a Graph Isomorphism Network encoder and a permutation-equivariant extension-level action head. Empirically, our method matches the known optima for planar realization counts and improves the best known bounds for spherical realization counts, yielding new record graphs. |
| title | Learning Minimally Rigid Graphs with High Realization Counts |
| topic | Machine Learning Combinatorics 52C25, 68R12 |
| url | https://arxiv.org/abs/2605.12427 |