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?
Embedding a graph in the euclidean space
reference request;graph algorithms;linear programming;embeddings
I finally managed to ask the person that originally told me about this approach. It appears to be closely related to maximum variance unfolding (MVU), see also https://en.wikipedia.org/wiki/Semidefinite_embedding. The paper introducing this approach is Learning a kernel matrix for nonlinear dimensionality reduction by Weinberger, Sha, and Saul if I am not mistaken.