<p>Suppose I have an undirected unweighted graph <span class="math-container">$G = (V,E)$</span>. Is there a way to compute points <span class="math-container">$x_v \in \mathbb{R}^d$</span> for each vertex <span class="math-container">$v \in V$</span> such that <span class="math-container">$||x_v - x_u|| = 1$</span> whenever <span class="math-container">$(u,v) \in E$</span> and <span class="math-container">$ ||x_v - x_u|| \geq C$</span> otherwise, for some constant <span class="math-container">$C &gt; 1$</span>?</p>

CC BY-SA 4.0
2019-07-03T11:58:51.240Z
Seems that you should be able to write an SDP for this. Search for vector programming and SDP and you will get several pointers.
Chandra Chekuri
CC BY-SA 4.0
2019-07-03T11:59:33.863Z
@ChandraChekuri Thanks!
Elliot Gorokhovsky
CC BY-SA 4.0
2019-07-03T12:26:50.940Z
Note that necessarily $d\geq n-1$, since for the complete graph you have to put all points at distance 1 from eachother. This corresponds to the "n-point uniform metric", mentioned e.g. [here](http://web.stanford.edu/class/cs369m/cs369mlecture1.pdf).
smapers
<graph-theory><cg.comp-geom><metric-spaces><embeddings>
Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor
Elliot Gorokhovsky
# Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor

(Asked by: username_0 on 2019-07-03)

Suppose I have an undirected unweighted graph $G = (V,E)$. Is there a way to compute points $x\_v \in \mathbb{R}^d$ for each vertex $v \in V$ such that $||x\_v - x\_u|| = 1$ whenever $(u,v) \in E$ and $ ||x\_v - x\_u|| \geq C$ otherwise, for some constant $C > 1$?

**Tags:** graph-theory, cg.comp-geom, metric-spaces, embeddings

> **Comments:**
> **username_1**: Seems that you should be able to write an SDP for this. Search for vector programming and SDP and you will get several pointers.  
> **username_0**: @ChandraChekuri Thanks!  
> **username_2**: Note that necessarily $d\geq n-1$, since for the complete graph you have to put all points at distance 1 from eachother. This corresponds to the "n-point uniform metric", mentioned e.g. [here](http://web.stanford.edu/class/cs369m/cs369mlecture1.pdf).  

---

## 0 answers

