Minimal combinatorial data needed to define a polytope

I don't know conditions of existence ($d$-connectivity is necessary), but the uniqueness was proved by Blind and Mani in 1987, see also the 1988 article "A simple way to tell a simple polytope from its graph" by Gil Kalai. Kalai's proof is also presented in Guenter Ziegler's book "Lectures on polytopes".

The simplicity assumption is important: for $d \ge 4$ there are different combinatorial classes of $1$-neighborly polytopes (polytopes whose $1$-skeleton is a complete graph).

In fact, elaborating on Guillermo Pineda-Villavicencio's answer, Jürgen Richter-Gebert's universality theorem for 4-polytopes shows that even in four dimensions, deciding whether a graph is realized by the vertices and edges of a simple polytope is equivalent to the existential theory of the reals.

I am fairly sure that the proof of this theorem can be extended to graphs of degree 4, so for an arbitrary semi-algebraic set defined by inequalities, you can in polynomial time find a graph so that the polytope is realizable if and only if this set is non-empty (although you should check this before you cite it in a paper).

See Realization spaces of 4-polytopes are universal by Richter-Gebert and Ziegler, although I suspect this theorem might have a better exposition in Richter-Gebert's monograph Realization Spaces of Polytopes.

Ivan Izmestiev's answer, and Blind and Mani's and Kalai's results, applies if you know beforehand that the graph is the graph of a d-dimensional polytope. There are many regular graphs, in the graph theoretical sense, that are not graphs of polytopes. See, for instance, the paper "Polytopality and cartesian products of graphs" by Pfeifle et al.