2006年
Enumerating non-crossing minimally rigid frameworks
COMPUTING AND COMBINATORICS, PROCEEDINGS
- ,
- ,
- ,
- ,
- 巻
- 4112
- 号
- 開始ページ
- 205
- 終了ページ
- 215
- 記述言語
- 英語
- 掲載種別
- 出版者・発行元
- SPRINGER-VERLAG BERLIN
In this paper we present an algorithm for enumerating without repetitions all the non-crossing generically minimally rigid bar-and-joint frameworks (simply called 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, with a slightly different implementation, in O(n(3)) time and O(n(2)) space. In particular, we obtain that the set of all non-crossing Laman frameworks 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.
- リンク情報
- ID情報
-
- ISSN : 0302-9743
- SCOPUS ID : 33749562399
- Web of Science ID : WOS:000240077300023