Counting Locally Flat-Foldable Origami Configurations Via 3-Coloring Graphs

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 mo...

Full description

Saved in:
Bibliographic Details
Published in:Graphs and combinatorics 2021, Vol.37 (1), p.241-261
Main Authors: Chiu, Alvin, Hoganson, William, Hull, Thomas C., Wu, Sylvia
Format: Article
Language:English
Subjects:
Combinatorial analysis
Combinatorics
Engineering Design
Enumeration
Graphs
Intersections
Mathematics
Mathematics and Statistics
Mountains
Original Paper
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 μ of a given flat-foldable crease pattern C , where locally valid means that each vertex will fold flat under μ 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.
ISSN:0911-0119
1435-5914
DOI:10.1007/s00373-020-02240-2