MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


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$

share|cite|improve this question
Dear Hans, what do you mean by a polygon and its polygonizations? – Gil Kalai Feb 2 '13 at 23:07
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. – Hans 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 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)

share|cite|improve this answer
@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)? – Hans Stricker Feb 2 '13 at 17:26
@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. – Joseph O'Rourke Feb 2 '13 at 18:31
For those who don't have a Springer account:… – Hans Stricker Feb 2 '13 at 23:39
@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.) – Hans Stricker Feb 3 '13 at 14:37
@Joseph: BTW, the second reference (to Rote) is a late answer to another question of mine:…. Thanks a lot for this one, too! – Hans Stricker Feb 3 '13 at 14:39

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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