Skip to main content
2 of 2
replaced http://mathoverflow.net/ with https://mathoverflow.net/

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

TerronaBell
  • 3.1k
  • 26
  • 29