# Embed graph in $\ell_2$ space so that edge and non-edge distances are separated by a constant factor

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$$?

• 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 Jul 3 '19 at 11:58
• @ChandraChekuri Thanks! – Elliot Gorokhovsky Jul 3 '19 at 11:59
• 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. – smapers Jul 3 '19 at 12:26