Flat Foldings of Plane Graphs with Prescribed Angles and Edge LengthsAbel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eppstein, David and Lubiw, Anna and Uehara, Ryuhei (2015) Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths. In: Graph Drawing 22nd International Symposium, GD 2014, September 2426, 2014 , pp. 272283(Official URL: http://dx.doi.org/10.1007/9783662458037_23). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783662458037_23
AbstractWhen 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 singlevertex flat origami with prescribed mountainvalley assignment, which corresponds to the case of a cycle graph. We characterize such flatfoldable 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 lineartime algorithm for testing flat foldability of plane graphs with prescribed edge lengths and angles, and a polynomialtime algorithm for counting the number of distinct folded states.
Actions (login required)
