Return to Answer

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)

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)

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, this 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)

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)

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)

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, this 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)