Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths

Abel, 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 24-26, 2014 , pp. 272-283(Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_23).

Full text not available from this repository.

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.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-662-45803-7_23
Classifications: G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.999 Others
M Methods > M.300 Dynamic / Incremental / Online
P Styles > P.540 Planar
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.250 Geometry
Z Theory > Z.750 Topology
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 22 May 2015 09:04
Last Modified: 23 Jun 2016 08:28
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1439

Actions (login required)

View Item View Item