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”, International Journal of Computational Geometry and Applications, volume 23, number 2, April 2013, pages 75–92.
- 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, it is known that such reconfiguration is not
always possible 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. Furthermore, we show that the equilateral constraint is
necessary for this result, by proving 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. 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 World Scientific.
- Availability:
- The paper is available in PDF (437k).
- See information on file formats.
- [Google Scholar search]
- Related papers:
- LinearEquilateral_ISAAC2011 (Folding Equilateral Plane Graphs)
See also other papers by Erik Demaine.
These pages are generated automagically from a
BibTeX file.
Last updated July 23, 2024 by
Erik Demaine.