By "Steinitz's theorem" I mean his theorem that a graph is the graph of a three-dimensional convex polyhedron iff it is of genus 0 and has a vertex connectivity of at least three. Can a similar characterization be made for genus 1, or beyond?



Generalizing Steinitz's theorem
Well, no direct generalization is known. One related result (which seems to have come out of an attempt to generalize Steinitz) is [this paper by D. Eppstein and E. Mumford.](http://arxiv.org/abs/0912.0537) However, since Steinitz' theorem is a simple consequence of the circle packing theorem, one can reasonably argue that the circle packing and its more general versions are the correct generalization -- unfortunately (or fortunately, for some of us) they move you into hyperbolic space. For recent work on this subject see the work of [Francois Fillastre.](http://arxiv.org/find/all/1/all%3a+Fillastre/0/1/0/all/0/1)


