5
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ Look at Joseph O'Rourke's answer to this question: mathoverflow.net/questions/7794/… $\endgroup$ Feb 8, 2014 at 23:48
  • $\begingroup$ Excellent. Thanks. So the only question remaining is the second one: do things get easier for simplicial graphs? $\endgroup$ Feb 8, 2014 at 23:54

4 Answers 4

7
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Feb 11, 2014 at 11:25
  • 2
    $\begingroup$ 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). $\endgroup$
    – Igor Pak
    Feb 11, 2014 at 20:55
3
$\begingroup$

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.

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

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:


         Cube.out.in
          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)

$\endgroup$
2
  • 1
    $\begingroup$ 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... $\endgroup$ Feb 9, 2014 at 1:59
  • $\begingroup$ P.S. Yes, I mean a triangulated surface. $\endgroup$ Feb 9, 2014 at 2:01
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.