Department of Applied Mathematics & Physics, Kyoto University

Technical Report 2008-012 (October 27, 2008)

Extending Steinitz' Theorem to Non-convex Polyhedra
by Seok-Hee Hong and Hiroshi Nagamochi

pdf File

The famous Steinitz' theorem of 1930's gives 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' theorem. We introduce upward polyhedra, which are defined as polyhedra such that 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. We give a graph-theoretic characterization of upward polyhedra; roughly speaking, they correspond to bi-connected planar graphs with some extra conditions. The proof of the characterization leads to an algorithm that constructs an upward polyhedron with n vertices in O(n^{1.5}) time. Moreover, one can test whether a given plane graph is an upward polyhedral graph in linear time. This is the first graph-theoretic characterization of polyhedra that are not necessarily convex.