| Enumerating planar minimally rigid graphs (2006) | |||||||||||||||
Abstract | |||||||||||||||
| Motivated by the work of Kawamoto et al. [5], who first suggested the use of graph enumeration techniques as an engineering tool for finding an optimum mechanism design, we give an algorithm for enumerating all the planar Laman graphs embedded on a given generic set p of n points. Our algorithm is based on the Reverse search paradigm of Avis and Fukuda [1]. 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. Figure 1: A non-planar Laman graph. A graph on n vertices is a Laman graph if it has exactly 2n − 3 edges and every subset of n ′ < n vertices spans at most 2n ′ − 3 edges. A classical result in Rigidity Theory [3], due to Laman, states that the underlying graphs of generic minimally rigid bar-and-joint frameworks in dimension 2 are exactly the Laman graphs. A planar minimally rigid framework on a given generic two-dimensional point set p is a Laman | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||