| Enumerating planar minimally rigid graphs (2006) | |||||||||||||||
Abstract | |||||||||||||||
| Abstract. We present an algorithm for enumerating without repetitions all the planar (noncrossing) minimally rigid (Laman) graphs embedded 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, with a slightly different implementation, in O(n 3) time and O(n 2) space. In particular, we obtain that the set of all planar Laman graphs on a given point set is connected by flips which remove an edge and then restore the Laman property with the addition of a non-crossing edge. 1 | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||