Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths
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...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2015
|
| Online Access: | http://hdl.handle.net/1721.1/100000 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 |
| _version_ | 1826216317877747712 |
|---|---|
| author | Demaine, Erik D. Demaine, Martin L. Eppstein, David Lubiw, Anna Uehara, Ryuhei Abel, Zachary Ryan |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Demaine, Erik D. Demaine, Martin L. Eppstein, David Lubiw, Anna Uehara, Ryuhei Abel, Zachary Ryan |
| author_sort | Demaine, Erik D. |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T16:45:29Z |
| format | Article |
| id | mit-1721.1/100000 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T16:45:29Z |
| publishDate | 2015 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/1000002022-09-29T21:20:44Z Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths Demaine, Erik D. Demaine, Martin L. Eppstein, David Lubiw, Anna Uehara, Ryuhei Abel, Zachary Ryan Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Abel, Zachary Ryan Demaine, Erik D. Demaine, Martin L. 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. National Science Foundation (U.S.) (ODISSEI Grant EFRI-1240383) National Science Foundation (U.S.) (Expedition Grant CCF-1138967) 2015-11-23T16:35:55Z 2015-11-23T16:35:55Z 2014 Article http://purl.org/eprint/type/JournalArticle 978-3-662-45802-0 978-3-662-45803-7 0302-9743 1611-3349 http://hdl.handle.net/1721.1/100000 Abel, Zachary, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, and Ryuhei Uehara. “Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths.” Lecture Notes in Computer Science (2014): 272–283. https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 en_US http://dx.doi.org/10.1007/978-3-662-45803-7_23 Graph Drawing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Demaine, Erik D. Demaine, Martin L. Eppstein, David Lubiw, Anna Uehara, Ryuhei Abel, Zachary Ryan Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths |
| title | Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths |
| title_full | Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths |
| title_fullStr | Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths |
| title_full_unstemmed | Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths |
| title_short | Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths |
| title_sort | flat foldings of plane graphs with prescribed angles and edge lengths |
| url | http://hdl.handle.net/1721.1/100000 https://orcid.org/0000-0003-3803-5703 https://orcid.org/0000-0002-4295-1117 |
| work_keys_str_mv | AT demaineerikd flatfoldingsofplanegraphswithprescribedanglesandedgelengths AT demainemartinl flatfoldingsofplanegraphswithprescribedanglesandedgelengths AT eppsteindavid flatfoldingsofplanegraphswithprescribedanglesandedgelengths AT lubiwanna flatfoldingsofplanegraphswithprescribedanglesandedgelengths AT uehararyuhei flatfoldingsofplanegraphswithprescribedanglesandedgelengths AT abelzacharyryan flatfoldingsofplanegraphswithprescribedanglesandedgelengths |