Question

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.

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$

Answer 1

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)

                

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)