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.
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Abbott, T.G., Demaine, E.D., Gassend, B.: arXiv:0901.1322 (January 2009), http://arxiv.org/abs/0901.1322
Abel, Z., Demaine, E.D., Demaine, M.L., Eisenstat, S., Lynch, J., Schardl, T.B., Shapiro-Ellowitz, I.: Folding equilateral plane graphs. Internat. J. Comput. Geom. Appl. 23(2), 75–92 (2013)
Alt, H., Knauer, C., Rote, G., Whitesides, S.: On the complexity of the linkage reconfiguration problem. In: Pach, J. (ed.) Towards a Theory of Geometric Graphs, Contemp. Math., vol. 342, pp. 1–13. Amer. Math. Soc., Providence (2004)
Arkin, E.M., Bender, M.A., Demaine, E.D., Demaine, M.L., Mitchell, J.S.B., Sethia, S., Skiena, S.S.: When can you fold a map? Comput. Geom. Th. Appl. 29(1), 23–46 (2004)
Ballinger, B., Charlton, D., Demaine, E.D., Demaine, M.L., Iacono, J., Liu, C.-H., Poon, S.-H.: Minimal locked trees. In: Dehne, F., Gavrilova, M., Sack, J.-R., Tóth, C.D. (eds.) WADS 2009. LNCS, vol. 5664, pp. 61–73. Springer, Heidelberg (2009)
Bern, M., Hayes, B.: The complexity of flat origami. In: Proc. 7th ACM-SIAM Symposium on Discrete Algorithms (SODA 1996), pp. 175–183 (1996)
Bertolazzi, P., Di Battista, G., Liotta, G., Mannino, C.: Upward drawings of triconnected digraphs. Algorithmica 12(6), 476–497 (1994)
Biedl, T., Demaine, E.D., Demaine, M.L., Lazard, S., Lubiw, A., O’Rourke, J., Robbins, S., Streinu, I., Toussaint, G., Whitesides, S.: A note on reconfiguring tree linkages: trees can lock. Discrete Appl. Math. 117(1-3), 293–297 (2002)
Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Algorithms & Appl. 11(1), 259–276 (2007)
Connelly, R., Demaine, E.D., Rote, G.: Infinitesimally locked self-touching linkages with applications to locked trees. In: Physical Knots: Knotting, Linking, and Folding Geometric Objects in ℝ3 (Las Vegas, NV, 2001). Contemp. Math., vol. 304, pp. 287–311. Amer. Math. Soc., Providence (2002)
Connelly, R., Demaine, E.D., Rote, G.: Straightening polygonal arcs and convexifying polygonal cycles. Discrete & Computational Geometry 30(2), 205–239 (2003)
Demaine, E.D., O’Rourke, J.: Geometric Folding Algorithms: Linkages, Origami, Polyhedra. Cambridge University Press (2007)
Di Battista, G., Nardelli, E.: Hierarchies and planarity theory. IEEE Trans. Systems Man Cybernet. 18(6), 1035–1046 (1988)
Duncan, C.A., Goodrich, M.T.: Planar orthogonal and polyline drawing algorithms. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, ch. 7, pp. 223–246. Chapman and Hall/CRC (2013)
Estrella-Balderrama, A., Fowler, J.J., Kobourov, S.G.: Characterization of unlabeled level planar trees. Comput. Geom. Th. Appl. 42(6-7), 704–721 (2009)
Garg, A.: New results on drawing angle graphs. Comput. Geom. Th. Appl. 9(1), 43–82 (1998)
Garg, A., Tamassia, R.: Upward planarity testing. Order 12(2), 109–133 (1995)
Garg, A., Tamassia, R.: On the computational complexity of upward and rectilinear planarity testing. SIAM J. Comput. 31(2), 601–625 (2001)
Harrigan, M., Healy, P.: Practical level planarity testing and layout with embedding constraints. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 62–68. Springer, Heidelberg (2008)
Hull, T.C.: The combinatorics of flat folds: a survey. In: Hull, T.C. (ed.) Origami3 (Asilomar, CA, 2001), pp. 29–38. A K Peters, Natick (2002)
Jünger, M., Leipert, S., Mutzel, P.: Level planarity testing in linear time. In: Whitesides, S.H. (ed.) GD 1998. LNCS, vol. 1547, p. 224. Springer, Heidelberg (1999)
Pach, J., Tóth, G.: Monotone drawings of planar graphs. J. Graph Theory 46(1), 39–47 (2004)
Ribó Mor, A.: Realization and counting problems for planar structures. Ph.D. thesis, Free Univ. Berlin (2006)
Saxe, J.: Embeddability of weighted graphs in k-space is strongly NP-hard. In: Proc. 17th Allerton Conf. Commun. Control Comput., pp. 480–489 (1979)
Schaefer, M.: Realizability of graphs and linkages. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 461–482. Springer, New York (2013)
Streinu, I., Whiteley, W.: Single-vertex origami and spherical expansive motions. In: Akiyama, J., Kano, M., Tan, X. (eds.) JCDCG 2004. LNCS, vol. 3742, pp. 161–173. Springer, Heidelberg (2005), http://dx.doi.org/10.1007/11589440_17
Tamassia, R.: On embedding a graph in the grid with the minimum number of bends. SIAM J. Comput. 16(3), 421–444 (1987)
Vijayan, G., Wigderson, A.: Rectilinear graphs and their embeddings. SIAM J. Comput. 14(2), 355–372 (1985)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abel, Z., Demaine, E.D., Demaine, M.L., Eppstein, D., Lubiw, A., Uehara, R. (2014). Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths. In: Duncan, C., Symvonis, A. (eds) Graph Drawing. GD 2014. Lecture Notes in Computer Science, vol 8871. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-662-45803-7_23
Download citation
DOI: https://doi.org/10.1007/978-3-662-45803-7_23
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-662-45802-0
Online ISBN: 978-3-662-45803-7
eBook Packages: Computer ScienceComputer Science (R0)