**Reference**:- Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, and Ryuhei Uehara, “Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths”, in
*Proceedings of the 22nd International Symposium on Graph Drawing (GD 2014)*, Würzburg, Germany, September 24–26, 2014, pages 272–283. **Abstract**:- 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.
**Comments**:- This paper is also available from SpringerLink, and as arXiv.org:1408.6771 of the Computing Research Repository (CoRR).
**Availability**:- The paper is available in PDF (833k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GraphFolding_JoCG (Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths)

See also other papers by Erik Demaine.

Last updated July 23, 2024 by Erik Demaine.