Counting Locally Flat-Foldable Origami Configurations Via 3-Coloring Graphs
- PDF / 827,478 Bytes
- 21 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 222 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Counting Locally Flat-Foldable Origami Configurations Via 3-Coloring Graphs Alvin Chiu1 • William Hoganson2 • Thomas C. Hull3
•
Sylvia Wu4
Received: 3 November 2019 / Revised: 19 September 2020 / Accepted: 9 October 2020 Springer Japan KK, part of Springer Nature 2020
Abstract Origami, where two-dimensional sheets are folded into complex structures, is rich with combinatorial and geometric structure, most of which remains to be fully understood. In this paper we consider flat origami, where the sheet of material is folded into a two-dimensional object, and consider the mountain (convex) and valley (concave) creases that result, called a MV assignment of the crease pattern. An open problem is to count the number locally valid MV assignments l of a given flat-foldable crease pattern C, where locally valid means that each vertex will fold flat under l with no self-intersections of the folded material. In this paper we solve this problem for a large family of crease patterns by creating a planar graph C whose 3-colorings are in one-to-one correspondence with the locally valid MV assignments of C. This reduces the problem of enumerating locally valid MV assignments to the enumeration of 3-colorings of graphs. Keywords Graph coloring Origami
Mathematics Subject Classification 05C15 52C99
& Thomas C. Hull [email protected] Alvin Chiu [email protected] William Hoganson [email protected] Sylvia Wu [email protected] 1
Georgia Institute of Technology, Atlanta, GA, USA
2
Swarthmore College, Swarthmore, PA, USA
3
Western New England University, Springfield, MA, USA
4
Clemson University, Clemson, SC, USA
123
Graphs and Combinatorics
1 Introduction Origami is the art of folding, allowing the transformation of flat pieces of paper, or any flat material, into two- or three-dimensional shapes. Enumerating the different ways to fold a flat sheet along straight crease lines into a flat object is an intriguing, open problem with applications in math, physics, and engineering [2, 5, 6]. Whenever paper is folded flat, the resulting straight line of the fold is a crease. An origami crease pattern (C, P) is a straight-line embedding of a planar graph C ¼ ðVðCÞ; EðCÞÞ on a region P of R2 , where the edges of C are the creases of the folded paper. Here we assume that P is bounded and the graph C is finite. Unless the shape of P is important we will refer to a crease pattern as just C. Giving the paper an arbitrary ‘‘top’’ and ‘‘bottom’’ when folding along the creases, each crease will either be a mountain crease (it bends the paper in a convex direction) or valley crease (it bends the paper in a concave direction). Thus, the flat-folded state of the paper is a mountain-valley (MV) assignment on C, which is a function l : EðCÞ ! f1; 1g, where lðcÞ ¼ 1 if the crease c is a mountain crease and lðcÞ ¼ 1 if it is a valley crease. We call an MV assignment l valid if it can be used to physically fold (C, P) flat such that the model could be pressed between
Data Loading...
