Ways to look at a polyhedral graph

Motivation

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

Question

I'd like to understand in an abstract setting:

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

Example

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.

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$

• 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-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)  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)

• @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-Peter 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: page.mi.fu-berlin.de/rote/Papers/slides/… – Hans-Peter 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-Peter Stricker Feb 3 '13 at 14:37
• @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! – Hans-Peter Stricker Feb 3 '13 at 14:39