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, but an answer was given only for the special case of complete graphs.)
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 Semide nite 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.
Just a remark: for convex surfaces (given by their intrinsic metrics) there is no good algorithm. The best heuristically is:
Alexandrov's theorem, weighted Delaunay triangulations, and mixed volumes AI Bobenko, I Izmestiev - arXiv preprint math/0609447, 2006 - arxiv.org
But still seems to be exponential.
This is not an answer, but I wanted to include an image in this comment.
I assume by "simplicial surface" you mean a triangulated surface, i.e., a surface all of whose faces are triangles. My hunch is that it is not easier for triangulated surfaces without further restrictions. For example, you might insist the surface be (a) closed, (b) embedded, and (c) have genus zero. Even with these restrictions, I suspect it is not fundamentally easier, because of the phenomenon illustrated below, which introduces exponential possibilities:
Therese Biedl, Anna Lubiw, Michael Spriggs. "Cauchy’s Theorem and Edge Lengths of Convex Polyhedra." 2007. (Springer link)
I wanted to add this as a comment but I don't have enough reputation points. For simplicial surfaces this is a very difficult question in general. In a recent paper (https://arxiv.org/abs/2204.02503) we proved that 4-connected nonspherical simplicial surfaces are generically globally rigid. When combined with a result of Connelly, Gortler and Theran (https://doi.org/10.1017/fms.2019.16) this implies that for generic weights, the point configuration is determined by a weights on a 4-connected simplicial surface graph. This only works for generic edge weightings however.
