Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths

Abel, Zachary and Demaine, Erik D. and Demaine, Martin L. and Eppstein, David and Lubiw, Anna and Uehara, Ryuhei (2015) Flat Foldings of Plane Graphs with Prescribed Angles and Edge Lengths. In: Graph Drawing 22nd International Symposium, GD 2014, September 24-26, 2014, Würzburg, Germany , pp. 272-283 (Official URL: http://dx.doi.org/10.1007/978-3-662-45803-7_23).

Full text not available from this repository.


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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-662-45803-7_23
Classifications:G Algorithms and Complexity > G.490 Embeddings
G Algorithms and Complexity > G.070 Area / Edge Length
G Algorithms and Complexity > G.999 Others
M Methods > M.300 Dynamic / Incremental / Online
P Styles > P.540 Planar
P Styles > P.720 Straight-line
P Styles > P.999 Others
Z Theory > Z.250 Geometry
Z Theory > Z.750 Topology
ID Code:1439

Repository Staff Only: item control page


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)