Flat foldings of plane graphs with prescribed angles and edge lengths

  • Zachary Abel Department of Mathematics, Massachusetts Inst. of Technology
  • Erik D. Demaine Computer Science and Artificial Intelligence Lab., Massachusetts Inst. of Technology
  • Martin L. Demaine Computer Science and Artificial Intelligence Lab., Massachusetts Inst. of Technology
  • David Eppstein University of California, Irvine
  • Anna Lubiw David R. Cheriton School of Computer Science, University of Waterloo
  • Ryuhei Uehara School of Information Science, Japan Advanced Institute of Science and Technology

Abstract

When can a plane graph with prescribed edge lengths and prescribed angles (from among $\{0,180^\circ,360^\circ\}$) 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^\circ$, 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.

Author Biography

David Eppstein, University of California, Irvine
Professor of Computer Science in the Donald Bren School of Information & Computer Sciences at the University of California, Irvine
Published
2018-02-27
How to Cite
Abel, Z., Demaine, E. D., Demaine, M. L., Eppstein, D., Lubiw, A., & Uehara, R. (2018). Flat foldings of plane graphs with prescribed angles and edge lengths. Journal of Computational Geometry, 9(1), 74–93. https://doi.org/10.20382/jocg.v9i1a3
Section
Articles

Most read articles by the same author(s)