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.