2023/06/20 by Eppstein, David
#Computational Geometry (cs.CG) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2306.11939
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.