How do I test whether a given undirected graph is the 1skeleton of a polytope?
How can I tell the dimension of a given 1skeleton?
How do I test whether a given undirected graph is the 1skeleton of a polytope? How can I tell the dimension of a given 1skeleton? 


A few comments: In general, you can't tell the dimension of a polytope from its graph. For any $n \geq 6$, the complete graph $K_n$ is the edge graph of both a $4$dimensional and a $5$dimensional polytope. (Thanks to dan petersen for correcting my typo.) The term for such polytopes is "neighborly". On the other hand, you can say that the dimension is bounded above by the lowest vertex degree occurring anywhere in the graph. A beautiful paper of Gil Kalai shows that, given a $d$regular graph, there is at most one way to realize it as the graph of a $d$dimensional polytope, and gives an explicit algorithm for reconstructing that polytope. You could try running his algorithm on your graph. (Or a more efficient version recently found by Friedman.) This algorithm will output some face lattice; that is to say, it will tell you which collections of vertices should be $2$faces, which should be $3$faces and so forth. Unfortunately, going from the face lattice to the polytope is very hard. According to the MathSciNet review, RichterGebert has shown that it is NPhard to, given a lattice of subsets of a finite set, decide whether it is the face lattice of a polytope. Note that this is a lower bound for the difficulty of your problem. Let me be more explicit about the last statement. RichterGebert shows that, given a collection $L$ of subsets of $[n]$, it is NPhard to determine whether there is a polytope with vertices labeled by $[n]$ whose edges, $2$faces and $3$faces are the given sets. (Here $[n] = \{ 1,2, \ldots, n \}$.) Suppose we had an algorithm to decide whether a graph could be the edge graph of a polytope. Take our collection $L$ and look at the twoelement sets within it. These form a graph with vertex set $[n]$. Run the algorithm on it. If the output is NO, then the answer to RichterGebert's problem is also no. If the answer is YES, then we have the problem that our algorithm might have found a polytope whose $2$faces and $3$faces differ from those prescribed by $L$. If our graph is $4$regular, this problem doesn't come up by Kalai's result. But, not having read RichterGebert myself, I don't know whether the problem is still NPhard when we restrict to $4$regular graphs. However, even if RichterGebert's result doesn't apply directly, I find it difficult to imagine that there could be an efficient algorithm to solve the graph realization problem, since there isn't one to solve the face lattice problem. 


A few more remarks, On the bright side: To determine if a given graph is the graph of a dpolytope is decidable. Tarski's algorithm for real closed fields can be used. In dimension 3 as Sam Nead mentioned graphs of 3polytopes are precisely 3 connected planar graphs. The algorithm by Hopcroft and Tarjan and various subsequent algorithms give a lineartime algorithm for planarity. Regarding the second question, it is possible that the same graph can be realized as the graph of dpolytopes of various dimensions. David already mentioned K_n which is the graph of a dpolytope for every d between 4 and n1. Another example is the graph of a dcube which was proved by Joswig and Ziegler to be a graph of epolytopes 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 dpolytopes with n vertices. See this paper of Benedetti and Ziegler. It is not known if this result extends to graphs of general dpolytopes, or to all subgraphs of graphs of simple dpolytopes, or to dual graphs of all triangulations of (d1)spheres. The later question is discussed by Gromov in the paper spaces and questions (p. 33). 


In dimension three there is the Steinitz theorem. 


Not an answer, but potentially useful:
("harmonious" == automorphisms of the graph induce rigid isometries the realization) When the graph has a high degree of symmetry, these realizations which I call "spectral"[*] have a great visual appeal; in general, though, these realizations are jumbles of points in onedimensional space. In most cases, multiple vertices (and edges) are collapsed to single points, so that the realizations aren't faithful. If a graph happens to admit a faithful spectral realization, you might be able to tease out a cell structure (which may not be unique), though I've not investigated this. I'll note that, even for polyhedra, there's no guarantee that the "faces" of a spectral realization are bounded by planar cycles of edges. [*] More precisely, the realizations as described here are orthogonal projections of realizations I call "spectral". (See my stilldrafty note, "Spectral Realizations of Graphs", the bulk of which is dedicated to a gallery of spectral realizations of the uniform polyhedra.) 

