A few more remarks, On the bright side: To determine if a given graph is the graph of a d-polytope is decidable. Tarski's algorithm for real closed fields can be used. 

Regarding the second question, it is possible that the same graph can be realized as the graph of d-polytopes of various dimensions. David already mentioned K_n which is the graph of a d-polytope for every d between 4 and n-1. Another example is the graph of a d-cube which was proved by [Joswig and Ziegler][1] to be a graph of e-polytopes for e between 4 and d.

Another fact is that there are not so many graphs of polytopes. There are only exponentially many different graphs of simple d-polytopes with n vertices. See [this paper of Benedetti and Ziegler][2]. It is not known if this result extends to graphs of general d-polytopes, or to all subgraphs of simple d-polytopes, or to dual graphs of all triangulations of (d-1)-spheres. The later question is discussed by Gromov in the paper [spaces and questions][3] (p. 33).


  [1]: http://front.math.ucdavis.edu/9812.5033
  [2]: http://front.math.ucdavis.edu/0902.0436
  [3]: http://www.ihes.fr/~gromov/topics/SpacesandQuestions.pdf