# A Comparison of Different Folding Models in Variations of the Map Folding Problem
## 5 Simple Folding Model in Total VOP  
It has been introduced in Section 1 that for an \(m\times n\) map, no matter if a single operation follows the simple folding model or the simple folding-unfolding model, the state before and after the operation would always be flat and in the shape of a rectangle. There already exists a method to decide the validity of given total overlapping orders with the simple folding-unfolding model. When the model changes to the simple folding model, it can be solved with a similar method, which maintains most of the existing one while with a little adjustment [16]. The adjustment is, when considering the order of the parallel crease lines supposed to be folded continuously, instead of using the folding-unfolding process introduced in [5], we repeat the reduction by finding the adjacent relation of neighbor squares to decide the next fold at each step. The conclusion is given as Theorem 2. The validity of the input total overlapping order with the simple folding model can be decided in O(mn) time. Proof of Theorem 2.: We first introduce the flow of the method, and then give the details on the adjustment. (1) Compute the MV assignment; (2) Decide the time points to change the folding direction to either horizontal or vertical. During each phase between two nearby time points, the map would be folded from a rectangular shape to a smaller rectangular shape with the length of one side fixed; (3) Viewing each partly flat-folded state as a new reduced map, a simple fold on a crease line should influence the overlapping order of all the neighbor pairs incident to this crease line in accordance. Traverse the input order to check for the unity and decide the folded state at every time point in (2); (4) Check the validity of the folded state at every time point. If all these computations are managed with all folded states tested as valid ones until the map is reduced to the size of \(1\times 1\), the input is valid. To apply the above process to the simple-folding model, we have to adjust (4) to check if the folded state at every time point is reachable by only simple folds. Since all the neighbor squares on the two sides of a single crease line (creases on a single line segment) are influenced by the folding of this crease line simultaneously, and their accordance is already checked in (3). We can view any partly flat-folded state as a 1D map. The check then becomes: given an input overlapping order of the segments separated by crease points, does it correspond to a valid folded-state of the simple-folding model? In this problem, all the lengths of the segments are integers. Using the same method as introduced in Section 4, the process will either tell that no available fold exists (invalid) or give the sequence of the simple folds leading to an input folded-state. Since every pair of neighbor squares would be handled only once according to this process, the check of (4) costs linear time in total. Following the above process, the validity of every partly flat-folded state can be checked, and the process totally costs \(O(mn)\) time, which is the same as the simple  
Figure 4: Three different cases of when gluing the \((k+1)\)-th square to a \(1\times k\) map. The dashed segments illustrate the \((k+1)\)-th square. (**a**) indicates the case where the \((k+1)\)-th square is adjacent to the \(k\)-th square; (**b**) indicates the case that the \(k\)-th square and the \((k+1)\)-th square are not adjacent and the end of the \((k+1)\)-th square is visible from outside; (**c**) indicates the case that the \(k\)-th square and the \((k+1)\)-th square are not adjacent and the end of the \((k+1)\)-th square is invisible from outside. folding-unfolding model. Because the other parts of the method remain the same, the total solution of the Total VOP with the simple folding model costs \(O(mn)\) time. Theorem 2 is proven. \(\square\)  
We give the computation for a 1 \(\times\) 20 map illustrated in Figure 3 as an example. The map is in length 20, and it comprises five segments \(l_{1}\) to \(l_{5}\) in order.