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 />
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
![alt text][2]
&nbsp;&nbsp;&nbsp;&nbsp;
![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])


  [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