Flat foldings of plane graphs with prescribed angles and edge lengths

• Abel, Zachary

• Demaine, Erik D.

• Demaine, Martin L.

• Eppstein, David

• Lubiw, Anna

• Uehara, Ryuhei

抄録

When can a plane graph with prescribed edge lengths and prescribed angles (from among {0,180∘,360∘}) be folded flat to lie in an infinitesimally thick line, without crossings? This problem generalizes the classic theory of single-vertex flat origami with prescribed mountain-valley assignment, which corresponds to the case of a cycle graph. We characterize such flat-foldable plane graphs by two obviously necessary but also sufficient conditions, proving a conjecture made in 2001: the angles at each vertex should sum to 360∘, and every face of the graph must itself be flat foldable. This characterization leads to a linear-time algorithm for testing flat foldability of plane graphs with prescribed edge lengths and angles, and a polynomial-time algorithm for counting the number of distinct folded states.

identifier:https://dspace.jaist.ac.jp/dspace/handle/10119/15360

収録刊行物

• Journal of Computational Geometry

  Journal of Computational Geometry 9 (1), 74-93, 2018

  Carleton University, Computational Geometry Laboratory

キーワード

• graph folding
• paper folding
• graph algorithm

詳細情報

• CRID: 1050564287491970432
• NII論文ID: 120006490003
• ISSN: 1920180X
• Web Site: http://hdl.handle.net/10119/15360
• 本文言語コード: en
• 資料種別: journal article
• データソース種別:
  • IRDB
  • CiNii Articles
  • KAKEN