Special Issue on Selected Papers from the 13th International Conference and Workshops on Algorithms and Computation, WALCOM 2019 Efficient Algorithm for Box Folding Koichi Mizunashi, Takashi Horiyama, and Ryuhei Uehara Vol. 24, no. 2, pp. 89-103, 2020. Regular paper. Abstract For a given polygon $P$ and a polyhedron $Q$, the folding problem asks if $Q$ can be obtained from $P$ by folding it. This simple problem is quite complicated, and there is no known efficient algorithm that solves this problem in general. In this paper, we focus on the case that $Q$ is a box, and the size of $Q$ is not given. That is, input of the box folding problem is a polygon $P$, and it asks if $P$ can fold to boxes of certain sizes. We note that there exist an infinite number of polygons $P$ that can fold into three boxes of different sizes. In this paper, we give a pseudo polynomial time algorithm that computes all possible ways of folding of $P$ to boxes. Submitted: April 2019. Reviewed: July 2019. Revised: August 2019. Accepted: October 2019. Final: January 2020. Published: February 2020. Communicated by Krishnendu Mukhopadhyaya and Shin-ichi Nakano article (PDF) BibTeX