Consider a graph $G$ with nonnegative edge weights.


**Question:** In $\mathbb{R}^3$, how hard is it to assign coordinates to vertices such that the Euclidean length of each edge is equal to its weight?


**Question:** Does it get any easier if $G$ is the 1-skeleton of a simplicial surface?


(A similar question was already answered [here](https://mathoverflow.net/questions/33043/algorithm-for-embedding-a-graph-with-metric-constraints), but an answer was given only for the special case of complete graphs.)



How hard is it to determine if a weighted graph can be isometrically embedded in R^3?
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](http://www1.se.cuhk.edu.hk/~manchoso/papers/thesis.pdf), Ph.D. thesis, Stanford, 2007.


I. Pak and D. Vilenchik, [Constructing uniquely realizable graphs](http://www.math.ucla.edu/~pak/papers/GRP4.pdf), 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](http://math.stanford.edu/~dankane/alexandrov.pdf), 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](https://math.stackexchange.com/questions/105330/equilateral-triangle-with-integer-coordinates) 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](http://www.math.ucla.edu/~pak/papers/pp16.pdf), Duke Math. J., vol. 129 (2005), 371-404.


