Autor:	Eppstein, David
Rok vydání:	2023
Předmět:	Computer Science - Computational Geometry Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	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. Comment: 8 pages, 8 figures. To appear at CCCG 2023
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2306.11939 Zobrazit plný text záznamu View this record from Arxiv