The Origami Flip Graph of the 2 x n Miura-ori

Abstract

Given an origami crease pattern C=(V,E), a straight-line planar graph embedded in a region of R², we assign each crease to be either a mountain crease (which bends convexly) or a valley crease (which bends concavely), creating a mountain-valley (MV) assignment µ : E –> {-1,1}. An MV assignment µ is locally valid if the faces around each vertex in C can be folded flat under µ. In this paper, we investigate locally valid MV assignments of the Miura-ori, M_m,n, an m x n parallelogram tessellation used in numerous engineering applications. The origami flip graph OFG(C) of C is a graph whose vertices are locally valid MV assignments of C, and two vertices are adjacent if they differ by a face flip, an operation that swaps the MV-parity of every crease bordering a given face of C. We enumerate the number of vertices and edges in OFG(M_2,n) and prove several facts about the degrees of vertices in OFG(M_2,n). By finding recurrence relations, we show that the number of vertices of degree d and 2n-a (for 0 ≤ a) are both described by polynomials of particular degrees. We then prove that the diameter of OFG(M_2,n) is the ceiling of n²/2 using techniques from 3-coloring reconfiguration graphs.