Extending Steinitz's Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra

In 1922, Steinitz's theorem gave a complete characterization of the topological structure of the vertices, edges, and faces of convex polyhedra as triconnected planar graphs. In this paper, we generalize Steinitz's theorem to non-convex polyhedra. More specifically, we introduce a new class of polyhedra, wider than convex polyhedra, called upward star-shaped polyhedra and spherical polyhedra, and present graph-theoretic characterization for both polyhedra. Upward star-shaped polyhedra are polyhedra where each face is star-shaped, all faces except the bottom face are visible from a view point, and any two faces sharing two vertices are non-coplanar. Spherical polyhedra are non-singular, non-coplanar polyhedra with no holes. We first present a graph-theoretic characterization of upward star-shaped polyhedra, i.e., characterization of upward star-shaped polyhedral graphs, which are the vertex-edge graphs (or 1-skeleton) of the upward star-shaped polyhedra. Roughly speaking, they correspond to biconnected planar graphs with special conditions. The proof of the characterization leads to an algorithm that constructs an upward star-shaped polyhedron with n vertices in O(n (1.5)) time. Moreover, one can test whether a given plane graph is an upward star-shaped polyhedral graph in linear time. We then present a graph-theoretic characterization of spherical polyhedra for planar cubic graphs, and planar graphs with maximum face size 4. We also formally define the Polyhedra Realizability Problem, and discuss its reducibility. Our result is the first graph-theoretic characterization of non-convex polyhedra, which solves an open problem posed by Grunbaum (Discrete Math. 307(3-5), 445-463, 2007), and a generalization of Steinitz's theorem (Polyeder und Raumeinteilungen, 1922), which characterized convex polyhedra as triconnected planar graphs.