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][1]) <br /> ![alt text][2] ![alt text][3] <br /> 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][4]) <hr /> 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][5]) [1]: http://www.eg-models.de/models/Polytopes/2003.08.001/_preview.html [2]: http://www.eg-models.de/models/Polytopes/2003.08.001/uninscribable_Preview.gif [3]: http://www.eg-models.de/models/Polytopes/2003.08.001/uninscribable_Schlegel.gif [4]: http://arxiv.org/abs/math.MG/9210218 [5]: http://link.springer.com/chapter/10.1007%252F978-3-642-25878-7_23?LI=true