Steinitz's Theorem for Star-Shaped Polytope Polyhedra


I generalised the classical theorem of Steinitz (1922) on convex polyhedra to upward star-shaped polyhedra. Convex polyhedra are aesthetically desirable, but not all graphs can be realised in this way; Steinitz's theorem, for 3D graph representations, has a strong "triconnectivity" assumption.
I produced the first graph-theoretic characterisation for non-convex polyhedra, by introducing "upward star-shaped polyhedra" and "spherical polyhedra". The proof of the characterisation leads to an efficient algorithm that constructs good non-convex polyhedral representations for biconnected graphs (i.e., good 3D representations of real-world networks). This result solved an open problem posed by Grunbaum in 2003 who fostered an interplay between geometry and combinatorics.


S. Hong and H. Nagamochi, "Extending Steinitz's Theorem to Upward Star-Shaped Polyhedra and Spherical Polyhedra", Algorithmica, Volume 61, Number 4, pp. 1022-1076, 2011.

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.


S. Hong and H. Nagamochi, "Upward Star-shaped Polyhedral Graphs", Proceedings of International Symposium on Algorithms and Computation (ISAAC 2009), Lecture Notes in Computer Science, Springer, pp. 913-922, 2009.