# How hard is it to determine if a weighted graph can be isometrically embedded in R^3?

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.)

-
Look at Joseph O'Rourke's answer to this question: mathoverflow.net/questions/7794/… – Yoav Kallus Feb 8 '14 at 23:48
Excellent. Thanks. So the only question remaining is the second one: do things get easier for simplicial graphs? – TerronaBell Feb 8 '14 at 23:54

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.

-
Great. (And thanks for some very interesting pointers.) So to summarize crudely: for general graphs it is hard but there are relaxations; for convex triangulated surfaces it can be solved efficiently for approximation but is hard or impossible to do exactly. No statement on the difficulty of finding approximate solutions for nonconvex surfaces. – TerronaBell Feb 11 '14 at 11:25
Actually, (3) applies to non-convex triangulated spheres as well. Of course, nothing is impossible, but even for the icosahedron with slightly perturbed edge lengths, the degrees of equations are not very encouraging (between 2^10 and 2^30). – Igor Pak Feb 11 '14 at 20:55

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:

Fig.23.2 in Geometric Folding Algorithms: Linkages, Origami, Polyhedra
It is certainly easier when you restrict attention to triangulated convex polyhedra, for then Cauchy's Rigidity Theorem applies. See, e.g.,

Therese Biedl, Anna Lubiw, Michael Spriggs. "Cauchy’s Theorem and Edge Lengths of Convex Polyhedra." 2007. (Springer link)

-
Thanks Joseph. Yes, these kinds of finite isometries do come to mind, though I don't yet have much intuition for whether they make it hard to find just one isometric embedding. From an optimization point of view: if the surface is infinitesimally rigid then any objective function with zeros only at isometric embeddings must be nonconvex (the zeros are isolated). But to answer the existence question, one may need only ski downhill to the bottom of a single valley... – TerronaBell Feb 9 '14 at 1:59
P.S. Yes, I mean a triangulated surface. – TerronaBell Feb 9 '14 at 2:01

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.

-
Nice paper! But here the distance they consider is the geodesic rather than Euclidean distance induced by the embedding, no? – TerronaBell Feb 9 '14 at 22:35
(E.g., in Figure 1 the extrinsic length of the arc will match the intrinsic length of the corresponding edge.) – TerronaBell Feb 9 '14 at 22:36
@TerronaBell yes, that is correct. – Igor Rivin Feb 11 '14 at 4:45