We develop an intrinsic necessary and sufficient condition for single-vertex origami crease patterns to be able to fold rigidly. We classify such patterns in the case where the creases are pre-assigned to be mountains and valleys as well as in the unassigned case. We also illustrate the utility of this result by applying it to the new concept of minimal forcing sets for rigid origami models, which are the smallest collection of creases that, when folded, will force all the other creases to fold in a prescribed way.
We describe a general family of curved-crease folding tessellations consisting of a repeating lens motif formed by two convex curved arcs. The third author invented the first such design in 1992, when he made both a sketch of the crease pattern and a vinyl model (pictured below). Curve fitting suggests that this initial design used circular arcs. We show that in fact the curve can be chosen to be any smooth convex curve without inflection point. We identify the ruling configuration through qualitative properties that a curved folding satisfies, and prove that the folded form exists with no additional creases, through the use of differential geometry.
In this paper, we study how to fold a specified origami crease pattern in order to minimize the impact of paper thickness. Specifically, origami designs are often expressed by a mountain-valley pattern (plane graph of creases with relative fold orientations), but in general this specification is consistent with exponentially many possible folded states. We analyze the complexity of finding the best consistent folded state according to two metrics: minimizing the total number of layers in the folded state (so that a flat folding is indeed close to flat), and minimizing the total amount of paper required to execute the folding (where thicker creases consume more paper). We prove both problems strongly NP-complete even for 1D folding. On the other hand, we prove the first problem fixed-parameter tractable in 1D with respect to the number of layers.
When can $t$ terminal pairs in an $m times n$ grid be connected by $t$ vertex-disjoint paths that cover all vertices of the grid? We prove that this problem is NP-complete. Our hardness result can be compared to two previous NP-hardness proofs: Lynchs 1975 proof without the ``cover all vertices constraint, and Kotsuma and Takenagas 2010 proof when the paths are restricted to have the fewest possible corners within their homotopy class. The latter restriction is a common form of the famous Nikoli puzzle emph{Numberlink}; our problem is another common form of Numberlink, sometimes called emph{Zig-Zag Numberlink} and popularized by the smartphone app emph{Flow Free}.
When can a plane graph with prescribed edge lengths and prescribed angles (from among ${0,180^circ, 360^circ$}) be folded flat to lie in an infinitesimally thin line, without crossings? This problem generalizes the classic theory of single-vertex flat origami with prescribed mountain-valley assignment, which corresponds to the case of a cycle graph. We characterize such flat-foldable plane graphs by two obviously necessary but also sufficient conditions, proving a conjecture made in 2001: the angles at each vertex should sum to $360^circ$, and every face of the graph must itself be flat foldable. This characterization leads to a linear-time algorithm for testing flat foldability of plane graphs with prescribed edge lengths and angles, and a polynomial-time algorithm for counting the number of distinct folded states.
Suppose that we are given two independent sets $I_b$ and $I_r$ of a graph such that $|I_b|=|I_r|$, and imagine that a token is placed on each vertex in $I_b$. Then, the sliding token problem is to determine whether there exists a sequence of independent sets which transforms $I_b$ into $I_r$ so that each independent set in the sequence results from the previous one by sliding exactly one token along an edge in the graph. This problem is known to be PSPACE-complete even for planar graphs, and also for bounded treewidth graphs. In this paper, we thus study the problem restricted to trees, and give the following three results: (1) the decision problem is solvable in linear time; (2) for a yes-instance, we can find in quadratic time an actual sequence of independent sets between $I_b$ and $I_r$ whose length (i.e., the number of token-slides) is quadratic; and (3) there exists an infinite family of instances on paths for which any sequence requires quadratic length.
