Zipper Unfolding of Domes and Prismoids

スポンサーリンク

概要

• 論文の詳細を見る

• We study Hamiltonian unfolding-cutting a convex polyhedron along a Hamiltonian path of edges to unfold it without overlap-of two classes of polyhedra. Such unfoldings could be implemented by a single zipper, so they are also known as zipper edge unfoldings. First we consider domes, which are simple convex polyhedra. We find a family of domes whose graphs are Hamiltonian, yet any Hamiltonian unfolding causes overlap, making the domes Hamiltonian-ununfoldable. Second we turn to prismoids, which are another family of simple convex polyhedra. We show that any nested prismoid is Hamiltonian-unfoldable, and that for general prismoids, Hamiltonian unfoldability can be tested in polynomial time.

• 2014-01-23

著者

• Ryuhei Uehara

  School Of Information Science Jaist

関連論文

• Efficient Enumeration of All Pseudoline Arrangements
• Hardness Results and an Exact Exponential Algorithm for the Spanning Tree Congestion Problem
• NP-completeness of generalized Kaboozle
• Computational Complexity of Piano-Hinged Dissections
• Bumpy Pyramid Folding Problem
• Zipper Unfolding of Domes and Prismoids
• Polynomial-Time Algorithms for Subgraph Isomorphism in Small Graph Classes of Perfect Graphs
• Intersection dimension of bipartite graphs
• FPT algorithms for Token Jumping on Graphs
• Common Unfolding of Regular Tetrahedron and Johnson-Zalgaller Solid

スポンサーリンク