五十嵐 悠紀さんの
Beady: Interactive Beadwork Design and Construction
を読みました。

Yuki Igarashi, Takeo Igarashi and Jun Mitani. Beady: Interactive Beadwork Design and Construction. ACM Transactions on Graphics (Proceedings of SIGGRAPH 2012), Volume 31, Issue 4, Article No. 49, Los Angels, USA, August 2012. PDF

Yuki Igarashi, Takeo Igarashi and Jun Mitani. “Beady: Interactive Beadwork Design and Construction” . ACM SIGGRAPH Asia 2011 Technical Sketch, Hong Kong, Dec. 2011. PDF (Interactive modeling only.)

五十嵐 悠紀,五十嵐 健夫,三谷 純:「インタラクティブなビーズデザインと制作支援」, 第19回インタラクティブシステムとソフトウェアに関するワークショップ (WISS2011), pp.48-53,京都天橋立, 2011年12月1-3日. PDF (Interactive modeling only.)

http://www.geocities.jp/igarashi_lab/beady/index-j.html

メモです。
(まちがっている点もあるかもしれません)

ビーズのつくりかた(レシピ)は、レシピ本などではこういうふうに2次元で表される。

http://allabout.co.jp/gm/gc/210807/2/より引用)

ある形状を構成するためのビーズを1本の糸で通せるかという問題は、
このビーズを頂点ととらえたグラフのハミルトンパスを探すという問題に置換できる。
が、あるグラフにハミルトンパスがあるかどうかを判定するのはNP完全。

そこで、そのかわりに、枝付きのspanning treeをつくる。
(spanning tree=スパニング木。スパニングツリーで検索してしまうと、ネットワーク用語のスパニングツリーがたくさん出てきてしまう)
スパニング木 http://ja.wikipedia.org/wiki/%E3%82%B9%E3%83%91%E3%83%8B%E3%83%B3%E3%82%B0%E6%9C%A8
ビーズ細工という特徴から、それでもできちゃうということみたい。

ちなみにこのCADでは、ビーズの部分は立体物の頂点ではなく面としてとらえられる。
その面を通る線(論文ではオレンジ色で表されている部分)をface stripと呼んでいるみたい。

つまりそのface stripに枝をつくる。