Flat Foldings of Plane Graphs with Prescribed Angles and Edge

When can a plane graph with prescribed edge lengths and prescribed angles (from among {0,180°, 360°}) be folded at to lie in an infinitesimally thick line, without crossings? This problem generalizes the classic theory of single-vertex at origami with prescribed mountain-valley assignment, which corresponds to the case of a cycle graph. We characterize such at-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 at foldable. This characterization leads to a linear-time algorithm for testing at foldability of plane graphs with prescribed edge lengths and angles, and a polynomial-time algorithm for counting the number of distinct folded states.Graph Drawing, 22nd International Symposium, GD 2014, Würzburg, Germany, September 24-26, 2014, Revised Selected Paper