There are at least three interpretations of an abstract polyhedral (= planar 3-vertex-connected) graph:

  • the 1-skeleton of a convex polyhedron (when embedded into $\mathbb{R}^3$)

  • a polygonization of the sphere (when embedded into the sphere $\mathbb{S}^2$)

  • a polygonization of a polygon – for each of its faces (when embedded into the plane $\mathbb{R}^2$)

In any case there are many geometric realizations:

  • of a polyhedron

  • of a polygonization of the sphere

  • of a polygon and its polygonizations


I'd like to understand in an abstract setting:

What do these interpretations and realizations have to do with each other?


For many (but not all) polyhedral graphs there is a realization as a convex polyhedron that is inscribable into the sphere. A central projection of this polyhedron back onto the sphere induces a polygonization of the sphere.

Taken for granted is Steinitz' theorem. The question is not about this.

EDIT: For completeness' sake I should mention embeddings of a polyhedral graph into:

  • the hyperbolic space $\mathbb{H}^2$

  • the 3-dimensional sphere $\mathbb{S}^3$

  • the hyperbolic space $\mathbb{H}^3$

  • $\begingroup$ Dear Hans, what do you mean by a polygon and its polygonizations? $\endgroup$ – Gil Kalai Feb 2 '13 at 23:07
  • $\begingroup$ Quite simple: every embedding of a planar graph into $\mathbb{R}^2$ has an outer face - "the polygon" - which is "polygonized" by the rest of the graph. $\endgroup$ – Hans-Peter Stricker Feb 2 '13 at 23:23

This is not a complete answer, just a pointer on one aspect of your question, the relationship between two of your three "interpretations." As you note, not all polyhedral graphs have a realization that is inscribable in a sphere. Here is an explicit example:

"Uninscribable 4-Regular Polyhedron." Electronic Geometry Model No. 2003.08.001. David Eppstein and Michael Dillencourt. (Link to abstract, and to the images below)

            alt text      alt text

There is a characterization of the inscribable polyhedral graphs, obtained in 1992:

Craig Hodgson, Igor Rivin, and Warren Smith. "A characterization of convex hyperbolic polyhedra and of convex polyhedra inscribed in the sphere." (arXiv link)

Now that I understand better the thrust of the question from the OP's comment below, I believe this recent survey by Günter Rote should be helpful:

"Realizing Planar Graphs as Convex Polytopes." Graph Drawing. Lecture Notes in Computer Science Volume 7034, 2012, pp 238-241. (Springer link)

  • $\begingroup$ @Joseph Thank you for the representation of polyhedrons by differently colored (shaded) faces and vertices. This helps a lot. Can this be automated (given an abstract polyhedral graph)? $\endgroup$ – Hans-Peter Stricker Feb 2 '13 at 17:26
  • $\begingroup$ @Hans: I have used Tutte's embedding theorem: Every 3-connected planar graph can be straight-line embedded in the plane so that each face is convex and each vertex a wheel. I'll add a reference to my answer. $\endgroup$ – Joseph O'Rourke Feb 2 '13 at 18:31
  • $\begingroup$ For those who don't have a Springer account: page.mi.fu-berlin.de/rote/Papers/slides/… $\endgroup$ – Hans-Peter Stricker Feb 2 '13 at 23:39
  • $\begingroup$ @Joseph: Do you know of a comparable result for inscribable polyhedral graphs in flat space $\mathbb{R}^3$? (I am not so familiar with hyperbolic space and have a lack of imagination.) $\endgroup$ – Hans-Peter Stricker Feb 3 '13 at 14:37
  • $\begingroup$ @Joseph: BTW, the second reference (to Rote) is a late answer to another question of mine: mathoverflow.net/questions/119455/…. Thanks a lot for this one, too! $\endgroup$ – Hans-Peter Stricker Feb 3 '13 at 14:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.