Name
Abstract | ||
|---|---|---|
When can a plane graph with prescribed edge lengths and prescribed angles (from among {0; 180 degrees; 360 degrees}) be folded flat to lie in an infinitesimally thin 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 degrees, 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. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/978-3-662-45803-7_23 | JOURNAL OF COMPUTATIONAL GEOMETRY |
DocType | Volume | Issue |
Journal | 9 | 1 |
ISSN | Citations | PageRank |
1920-180X | 0 | 0.34 |
References | Authors | |
17 | 6 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Zachary Abel | 1 | 57 | 10.42 |
| Erik D. Demaine | 2 | 4624 | 388.59 |
| Martin L. Demaine | 3 | 592 | 84.37 |
| David Eppstein | 4 | 4897 | 533.94 |
| Anna Lubiw | 5 | 753 | 95.36 |
| Ryuhei Uehara | 6 | 528 | 75.38 |