Maximal origami flip graphs of flat-foldable vertices: properties and algorithms
share
Flat origami studies straight line, planar graphs C=(V,E) drawn on a region R⊂ℝ^2 that can act as crease patterns to map, or fold, R into ℝ^2 in a way that is continuous and a piecewise isometry exactly on the faces of C. Associated with such crease pattern graphs are valid mountain-valley (MV) assignments μ:E→{-1,1}, indicating which creases can be mountains (convex) or valleys (concave) to allow R to physically fold flat without self-intersecting. In this paper, we initiate the first study of how valid MV assignments of single-vertex crease patterns are related to one another via face-flips, a concept that emerged from applications of origami in engineering and physics, where flipping a face F means switching the MV parity of all creases of C that border F. Specifically, we study the origami flip graph OFG(C), whose vertices are all valid MV assignments of C and edges connect assignments that differ by only one face flip. We prove that, for the single-vertex crease pattern A_2n whose 2n sector angles around the vertex are all equal, OFG(A_2n) contains as subgraphs all other origami flip graphs of degree-2n flat origami vertex crease patterns. We also prove that OFG(A_2n) is connected and has diameter n by providing two O(n^2) algorithms to traverse between vertices in the graph, and we enumerate the vertices, edges, and degree sequence of OFG(A_2n). We conclude with open questions on the surprising complexity found in origami flip graphs of this type.
READ FULL TEXT