Paper by Erik D. Demaine

Reference:

Zachary Abel, Erik D. Demaine, Martin L. Demaine, David Eppstein, Anna Lubiw, and Ryuhei Uehara, “Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths”, Journal of Computational Geometry, volume 9, number 1, 2018, pages 74–93.

BibTeX

@Article{GraphFolding_JoCG,
  AUTHOR        = {Zachary Abel and Erik D. Demaine and Martin L. Demaine and David Eppstein and Anna Lubiw and Ryuhei Uehara},
  TITLE         = {Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths},
  JOURNAL       = {Journal of Computational Geometry},
  journalurl    = {http://jocg.org/},
  VOLUME        = 9,
  NUMBER        = 1,
  YEAR          = 2018,
  PAGES         = {74--93},

  withstudent   = 1,
  replaces      = {GraphFolding_GD2014},
  papers        = {GraphFolding_GD2014},
  doi           = {https://dx.doi.org/10.20382/jocg.v9i1a3},
  dblp          = {https://dblp.org/rec/journals/jocg/AbelDDELU18},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.20382/jocg.v9i1a3">JoCG</A>,
                   and as
                   <A HREF="http://arXiv.org/abs/1408.6771">
                   arXiv.org:1408.6771</A> of the
                   <A HREF="http://arXiv.org/archive/cs/intro.html">
                   Computing Research Repository (CoRR)</A>.},
}

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.

Comments:

This paper is also available from JoCG, and as arXiv.org:1408.6771 of the Computing Research Repository (CoRR).

Availability:

The paper is available in PDF (1625k).

See information on file formats.

[Google Scholar search]

Related papers:

GraphFolding_GD2014 (Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths)