Origami fold as algebraic graph rewriting

We formalize paper fold (origami) by graph rewriting. Origami construction is abstractly described by a rewriting system (O,↬), where O is the set of abstract origamis and ↬ is a binary relation on O, that models fold. An abstract origami is a structure (Π,∽,≻), where Π is a set of faces constituting an origami, and ∽ and ≻ are binary relations on Π, each representing adjacency and superposition relations between the faces.We then address representation and transformation of abstract origamis and further reasoning about the construction for computational purposes. We present a labeled hypergraph of origami and define fold as algebraic graph transformation. The algebraic graph-theoretic formalism enables us to reason about origami in two separate domains of discourse, i.e. pure combinatorial domain where symbolic computation plays the main role and geometrical domain R×R. We detail the program language for the algebraic graph rewriting and graph rewriting algorithms for the fold, and show how fold is expressed by a set of graph rewrite rules.