A Parameterized Algorithm for Flat Folding

06/20/2023
by   David Eppstein, et al.
0

We prove that testing the flat foldability of an origami crease pattern (either labeled with mountain and valley folds, or unlabeled) is fixed-parameter tractable when parameterized by the ply of the flat-folded state and by the treewidth of an associated planar graph, the cell adjacency graph of an arrangement of polygons formed by the flat-folded state. For flat foldings of bounded ply, our algorithm is single-exponential in the treewidth; this dependence on treewidth is necessary under the exponential time hypothesis.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset