Enumerating Constrained Non-crossing Minimally Rigid Frameworks
| dc.creator | Avis, David | |
| dc.creator | Katoh, Naoki | |
| dc.creator | Ohsaki, Makoto | |
| dc.creator | Streinu, Ileana | |
| dc.creator | Tanigawa, Shin-ichi | |
| dc.date | 2006-08-03 | |
| dc.date | 2006-11-07 | |
| dc.date.accessioned | 2026-07-07T07:21:22Z | |
| dc.date.available | 2026-07-07T07:21:22Z | |
| dc.description | In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks under edge constraints (also called constrained non-crossing Laman frameworks) on a given generic set of $n$ points. Our algorithm is based on the reverse search paradigm of Avis and Fukuda. It generates each output graph in $O(n^4)$ time and O(n) space, or, slightly different implementation, in $O(n^3)$ time and $O(n^2)$ space. In particular, we obtain that the set of all the constrained non-crossing Laman frameworks on a given point set is connected by flips which restore the Laman property. | |
| dc.description | 14 pages, 3 figures | |
| dc.identifier | https://arxiv.org/abs/math/0608102 | |
| dc.identifier | http://arxiv.org/abs/math/0608102 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/115280 | |
| dc.subject | Combinatorics | |
| dc.subject | 68W01 | |
| dc.title | Enumerating Constrained Non-crossing Minimally Rigid Frameworks | |
| dc.type | text |