<p>Given any undirected edge-weighted graph (with weights > 0) and some dimension d, is there a way to assign positions in $\mathbb{R}^d$ to those vertices such that all of the edges between them have euclidean distance equal to their weights?</p>

<p>The resulting edges may be crossing, that is okay. I'm really interested in the decision problem of when it is or isn't possible but an efficient algorithm to do it when it is possible would also be nice.</p>

CC BY-SA 3.0
2017-03-22T17:49:32.327Z
You can find what you're looking for here [http://convexoptimization.com/TOOLS/cutbook.pdf] in chapter 6.
Samuel Schlesinger
CC BY-SA 3.0
2017-03-22T19:06:37.777Z
If you fix the dimension d to be less than $n$ the problem is NP-Hard. However, if you only want to know whether there is an embedding into Euclidean space such that the distances are preserved exactly then one can solve this in polynomial time via seme-definite programming. This holds true only for Euclidean distances.
Chandra Chekuri
CC BY-SA 3.0
2017-03-24T14:16:32.603Z
No efficient algorithm is possible unless $P=NP$. Your problem is hard even for a very restricted case of binary trees (all edges have weight 1). It is NP-complete to decide the existence of an embedding of binary tree in 2D grid such that all edges have unit length.
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-03-25T12:03:48.043Z
What kind of spaces are you interested in?  Are you interested in metric spaces? How do you define length in your space?
Mohammad Al-Turkistany
CC BY-SA 3.0
2017-03-27T20:30:00.537Z
@ChandraChekuri You're right! That's cool :) The reduction ends up being pretty trivial but I might write it up as an answer if you don't want to alongside a simple interior point method for completeness.
Phylliida
CC BY-SA 3.0
2017-03-27T20:31:52.907Z
@MohammadAl-Turkistany I'm interested in the L2 and L1 norm though I am curious what answers to this question are for other metric spaces.
Phylliida
<graph-theory><graph-algorithms><embeddings>
Embedding a graph with specified edge lengths in d-dimensional space
Phylliida
# Embedding a graph with specified edge lengths in d-dimensional space

(Asked by: username_0 on 2017-03-22)

Given any undirected edge-weighted graph (with weights > 0) and some dimension d, is there a way to assign positions in $\mathbb{R}^d$ to those vertices such that all of the edges between them have euclidean distance equal to their weights?

The resulting edges may be crossing, that is okay. I'm really interested in the decision problem of when it is or isn't possible but an efficient algorithm to do it when it is possible would also be nice.

**Tags:** graph-theory, graph-algorithms, embeddings

> **Comments:**
> **username_1**: You can find what you're looking for here [http://convexoptimization.com/TOOLS/cutbook.pdf] in chapter 6.  
> **username_2**: If you fix the dimension d to be less than $n$ the problem is NP-Hard. However, if you only want to know whether there is an embedding into Euclidean space such that the distances are preserved exactly then one can solve this in polynomial time via seme-definite programming. This holds true only for Euclidean distances.  
> **username_3**: No efficient algorithm is possible unless $P=NP$. Your problem is hard even for a very restricted case of binary trees (all edges have weight 1). It is NP-complete to decide the existence of an embedding of binary tree in 2D grid such that all edges have unit length.  
> **username_3**: What kind of spaces are you interested in?  Are you interested in metric spaces? How do you define length in your space?  
> **username_0**: @ChandraChekuri You're right! That's cool :) The reduction ends up being pretty trivial but I might write it up as an answer if you don't want to alongside a simple interior point method for completeness.  
> **username_0**: @MohammadAl-Turkistany I'm interested in the L2 and L1 norm though I am curious what answers to this question are for other metric spaces.  

---

## 0 answers

