论文标题
最大折纸折叠顶点的折纸翻转图：属性和算法
Maximal origami flip graphs of flat-foldable vertices: properties and algorithms
论文作者
论文摘要
平坦的折纸研究直线，平面图$ c =（v，e）$在区域$ r \ r \ subset \ mathbb {r}^2 $上，可以用作绘制的折痕模式，或以$ \ m $ \ mathbb {r}^2 $折叠，以连续的和faces $ c $ c $ c $ c $ c $ c。与此类折痕图案图相关的是有效的山谷（MV）分配$μ：在本文中，我们首次研究了单个Vertex折痕模式的有效MV分配是如何通过面部浮雕彼此相关的，这一概念来自折纸在工程和物理学中的应用中的应用，其中翻转face $ f $意味着切换所有$ c $ F $ f $ $ f $ $ c $的MV平价。具体来说，我们研究了折纸翻转图$ {\ rm {ofg}}（c）$，其顶点都是$ c $的有效MV分配，并且边缘连接仅通过一个脸部翻转的分配。 We prove that, for the single-vertex 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.我们还证明$ {\ rm {ofg}}（a_ {2n}）$是连接的，并通过提供两个$ o（n^2）$算法的直径$ n $连接，以在图中的顶点之间穿越，我们枚举了$ {\ rm rm {a = n of the Edges，edges，edges，edges and edges，edge and effertices and edges，edges and a = a =我们以对这种类型的折纸翻转图中令人惊讶的复杂性的开放性问题结束。
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 mountain-valley (MV) assignments $μ:E\to\{-1,1\}$, indicating which creases can be mountains (convex) or valleys (concave) to allow $R$ to physically fold flat without self-intersecting. In this paper, we initiate the first study of how valid MV assignments of single-vertex crease patterns are related to one another via face-flips, 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 single-vertex 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.
