There are several possible ways to interpret your question. Let me mention three, all very different:

**(1)** For general graphs, say you want to decide if there is such realization at all, and if yes find it approximately. This is called *Graph Realization Problem* and it is well studied both theoretically and practically (e.g. it is easily NP-hard). For general references see So's thesis, and for connection to graph colorings our paper below.

A. So, A Semidenite Programming Approach to the Graph Realization Problem, Ph.D. thesis, Stanford, 2007.

I. Pak and D. Vilenchik, Constructing uniquely realizable graphs, Discrete & Computational Geometry, vol. 50 (2013), 1051-1071.

**(2)** For triangulated surfaces, say you want to approximately compute the convex realization (the decision problem is easy by the Alexandrov theorem). This is done by a recent analysis of the Bobenko-Izmestiev algorithm mentioned in the Igor Rivin's answer:

D. Kane, G. Price, E. Demaine, A Pseudopolynomial Algorithm for Alexandrov’s Theorem, Algorithms and Data Structures, Lecture Notes in CS, Vol. 5664, 2009, pp 435-446.

**(3)** For triangulated surfaces, say you want to compute the *exact* vertex coordinates. First, note that even in $\Bbb R^2$ the equilateral triangle cannot be realized using rational coordinates. What happens is that you are solving a large system of quadratic equations. The vertex coordinates are then solutions of equations of large degree with coefficients being polynomials in squared edge-lengths. In our paper with Fedorchuk we use a Bezout's theorem type argument to show that the upper bound on these degrees is $2^m$, where $m=3n-6$ is the number of edges of the triangulated surfaces with $n$ vertices. Note that for even the most trivial triangulated surfaces such as the cyclic polytope (think of a "snake of tetrahedra") there is a natural exponential lower bound $2^{n-4}$, see the paper.

M. Fedorchuk and I. Pak, Rigidity and polynomial invariants of convex polytopes, Duke Math. J., vol. 129 (2005), 371-404.