# Embedding a graph in the euclidean space

Given a graph $G=(V,E)$, find a mapping $f\colon V \rightarrow \mathbb R^d$ such that for every edge $(u,v) \in E$ we have that $||f(u)-f(v)|| \leq r$; and for every $(u,v) \not \in E$, we have the opposite $||f(u)-f(v)|| > r$ for some given $r$. One could also view this problem as embedding a unit disc graph back into the euclidean space.

Now I have been told that - while the problem is NP-complete - the usual way to do it is as follows. This is where the hearsay starts, so excuse me if I am a little vague.

The proposed approach places an arbitrary node at $0$. Then, run a linear (or quadratic?) program that maximizes $\sum_{v \in V} g(f(v))$ under the side condition stated above, i.e. for all edges $(u,v) \in E$, $(f(u) - f(v))^2 \leq r^2$. $g$ is probably some norm, maybe $L_1$ or $L_2$.

This is how I more or less understood it. The general gist was to fix the position of an initial node and then "spread" the graph apart using the linear program.

I tried to find some sources on that, maybe a paper that introduced this approach, but so far my efforts failed - there are just too many ways to embed a graph in the $\mathbb R^d$. In particular, I am interested in how this approach deals with noisy data. For example, consider a grid graph of size $n \times n$ which should be perfectly embeddable in the euclidean plane. Now, add an edge from $(0,0)$ to $(n,n)$. Intuitively, in an embedding I would like to ignore the edge since the rest of the graph is a perfect grid. The approach above, however, would most likely produce a weird embedding.

Can anyone give me some pointers to work describing this approach?

• So what is your question? – cody Jun 2 '15 at 20:16
• I'm mainly looking for some paper introducing this approach. Any literature would be appreciated. – HdM Jun 2 '15 at 20:23
• – Sariel Har-Peled Jun 3 '15 at 20:16
• Could you expand on that? I know of MDS, do you see a way to incorporate the above approach in some multi dimensional scaling? – HdM Jun 3 '15 at 21:42