Skip to main content
MathOverflow

Return to Question

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link
Community Bot
Community Bot
  • 1
  • 2
  • 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 herehere, but an answer was given only for the special case of complete graphs.)

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

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

Source Link
TerronaBell
TerronaBell
  • 3.1k
  • 26
  • 29

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