MISC

2006年

Enumerating non-crossing minimally rigid frameworks

COMPUTING AND COMBINATORICS, PROCEEDINGS
  • David Avis
  • ,
  • Naoki Katoh
  • ,
  • Makoto Ohsaki
  • ,
  • Ileana Streinu
  • ,
  • Shin-ichi Tanigawa

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.

リンク情報
Web of Science
https://gateway.webofknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=JSTA_CEL&SrcApp=J_Gate_JST&DestLinkType=FullRecord&KeyUT=WOS:000240077300023&DestApp=WOS_CPL
URL
http://www.scopus.com/inward/record.url?partnerID=HzOxMe3b&scp=33749562399&origin=inward
ID情報
  • ISSN : 0302-9743
  • SCOPUS ID : 33749562399
  • Web of Science ID : WOS:000240077300023

エクスポート
BibTeX RIS