Zhao, HuiLi, XuanWang, WenchengWang, XiaolingWang, ShaodongLei, NaGu, XianfengLee, Jehee and Theobalt, Christian and Wetzstein, Gordon2019-10-142019-10-1420191467-8659https://doi.org/10.1111/cgf.13839https://diglib.eg.org:443/handle/10.1111/cgf13839There are many methods proposed for generating polycube polyhedrons, but it lacks the study about the possibility of generating polycube polyhedrons. In this paper, we prove a theorem for characterizing the necessary condition for the skeleton graph of a polycube polyhedron, by which Steinitz's theorem for convex polyhedra and Eppstein's theorem for simple orthogonal polyhedra are generalized to polycube polyhedra of any genus and with non-simply connected faces. Based on our theorem, we present a faster linear algorithm to determine the dimensions of the polycube shape space for a valid graph, for all its possible polycube polyhedrons. We also propose a quadratic optimization method to generate embedding polycube polyhedrons with interactive assistance. Finally, we provide a graph-based framework for polycube mesh generation, quadrangulation, and all-hex meshing to demonstrate the utility and applicability of our approach.Mathematics of computingGraphs and surfacesComputing methodologiesMesh modelsMesh geometry models10.1111/cgf.13839311-322