Paper by Erik D. Demaine

Reference:

Zachary Abel, Erik D. Demaine, Martin L. Demaine, Sarah Eisenstat, Jayson Lynch, Tao B. Schardl, and Isaac Shapiro-Ellowitz, “Folding Equilateral Plane Graphs”, in Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC 2011), Lecture Notes in Computer Science, volume 7074, December 5–8, 2011, pages 574–583.

BibTeX

@InProceedings{LinearEquilateral_ISAAC2011,
  AUTHOR        = {Zachary Abel and Erik D. Demaine and Martin L. Demaine and
                   Sarah Eisenstat and Jayson Lynch and Tao B. Schardl and
                   Isaac Shapiro-Ellowitz},
  TITLE         = {Folding Equilateral Plane Graphs},
  BOOKTITLE     = {Proceedings of the 22nd International Symposium on
                   Algorithms and Computation (ISAAC 2011)},
  bookurl       = {http://www.is.titech.ac.jp/isaac11/},
  MONTH         = {December 5--8},
  YEAR          = 2011,
  PAGES         = {574--583},
  SERIES        = {Lecture Notes in Computer Science},
  seriesurl     = {http://www.springer.de/comp/lncs/},
  VOLUME        = 7074,

  withstudent   = 1,
  doi           = {https://dx.doi.org/10.1007/978-3-642-25591-5_59},
  dblp          = {https://dblp.org/rec/conf/isaac/AbelDDELSS11},
  comments      = {This paper is also available from <A HREF="http://dx.doi.org/10.1007/978-3-642-25591-5_59">SpringerLink</A>.},
  papers        = {LinearEquilateral_IJCGA},
}

Abstract:

We consider two types of folding applied to equilateral plane graph linkages. First, under continuous folding motions, we show how to reconfigure any linear equilateral tree (lying on a line) into a canonical configuration. By contrast, such reconfiguration is known to be impossible for linear (nonequilateral) trees and for (nonlinear) equilateral trees. Second, under instantaneous folding motions, we show that an equilateral plane graph has a noncrossing linear folded state if and only if it is bipartite. Not only is the equilateral constraint necessary for this result, but we show that it is strongly NP-complete to decide whether a (nonequilateral) plane graph has a linear folded state. Equivalently, we show strong NP-completeness of deciding whether an abstract metric polyhedral complex with one central vertex has a noncrossing flat folded state with a specified “outside region”. By contrast, the analogous problem for a polyhedral manifold with one central vertex (single-vertex origami) is only weakly NP-complete.

Comments:

This paper is also available from SpringerLink.

Availability:

The paper is available in PDF (304k).

See information on file formats.

[Google Scholar search]

Related papers:

LinearEquilateral_IJCGA (Folding Equilateral Plane Graphs)