A parameterized algorithm for flat folding.
D. Eppstein.
arXiv:2306.11939.
Proc. 35th Canadian Conference on Computational Geometry, 2023, pp. 35–42.
Testing whether an origami folding pattern can be folded flat is fixed-parameter tractable when parameterized by two parameters: the ply (maximum number of layers) of the folding, and the treewidth of a planar graph describing the arrangement of polygons in the flat-folded result. The dependence on treewidth is optimal under the exponential-time hypothesis.
Merged into "Computational complexities of folding" for journal submission.