Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00605
Maximal origami flip graphs of flatfoldable vertices: properties and algorithms
Vol. 26, no. 4, pp. 503517, 2022. Regular paper.
Abstract Flat origami studies straight line, planar graphs $C=(V,E)$ drawn on a region $R\subset\mathbb{R}^2$ that can act as crease patterns to map, or fold, $R$ into $\mathbb{R}^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 mountainvalley (MV) assignments $\mu:E\to\{1,1\}$, indicating which creases can be mountains (convex) or valleys (concave) to allow $R$ to physically fold flat without selfintersecting. In this paper, we initiate the first study of how valid MV assignments of singlevertex crease patterns are related to one another via faceflips, 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 $\rm{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 singlevertex crease pattern $A_{2n}$ whose $2n$ sector angles around the vertex are all equal, $\rm{OFG}(A_{2n})$ contains as subgraphs all other origami flip graphs of degree$2n$ flat origami vertex crease patterns. We also prove that $\rm{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 $\rm{OFG}(A_{2n})$. We conclude with open questions on the surprising complexity found in origami flip graphs of this type.
This work is licensed under the terms of the CCBY license.

Submitted: August 2021.
Reviewed: June 2022.
Revised: July 2022.
Accepted: September 2022.
Final: September 2022.
Published: September 2022.
Communicated by
Anna Lubiw

Journal Supporters
