Can you determine whether a graph is the 1-skeleton of a polytope?

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, Richter-Gebert has shown that it is NP-hard 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. Richter-Gebert shows that, given a collection $L$ of subsets of $[n]$, it is NP-hard 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 two-element 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 Richter-Gebert'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 Richter-Gebert myself, I don't know whether the problem is still NP-hard when we restrict to $4$-regular graphs.

However, even if Richter-Gebert'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.