**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”,
*Journal of Computational Geometry*, volume 9, number 1, 2018, pages 74–93. **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 JoCG, and as arXiv.org:1408.6771 of the Computing Research Repository (CoRR).
**Availability**:- The paper is available in PDF (1625k).
- See information on file formats.
- [Google Scholar search]
**Related papers**:- GraphFolding_GD2014 (Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths)

See also other papers by Erik Demaine.

Last updated February 26, 2024 by Erik Demaine.