# Isomorphic graph embeddings in the Euclidean Space

Given an undirected and unweighted graph $$G = (V, E)$$, is it possible to find a mapping $$f: V \rightarrow \mathbb{R}^k$$ for some $$k$$ such that for every $$i, j \in V$$, $$\|f(i) - f(j)\|_2^2 = \Delta(i, j)$$, where $$\Delta(i, j)$$ is the shortest path length between $$i$$ and $$j$$ in $$G$$?

I have been testing a few counterexamples for which these isometric embeddings in $$\ell_2$$ fail to exist (for example, the 4-cycle), but in this case they work.

• Notice that the standard metric over the Euclidean space is the $\ell_2$-norm $\|f(i)-f(j)\|_2$, rather than $\|f(i)-f(j)\|_2^2$. Any reason why you consider the squared $\ell_2$-norm? – smapers Aug 19 at 14:52
• @smapers Because of the second paragraph? – Emil Jeřábek Aug 19 at 14:56
• Oh, ofcourse, thanks! – smapers Aug 19 at 14:59
• Metric embeddings is a well-explored topic. See book by Deza-Laurent springer.com/gp/book/9783540616115 or a web search will reveal several lecture notes and papers on this topic. Square distance embeddings are negative type metrics and one can in fact test, via semi-definite-programming, whether one can embed a given finite metric into a Euclidean space (no restriction on dimension). Many problems here are also NP-Hard. – Chandra Chekuri Aug 19 at 19:29
• Thanks Chandra, the pointer turned out to be useful. I'm not an expert of the field and the only relevant theorem I was aware of is due to Schoenberg (ams.org/journals/tran/1938-044-03/S0002-9947-1938-1501980-0/…) but it is quite complicate to work with. – Andrea Aug 20 at 14:19

The 4-cycle is actually helpful to consider: embedding it in $$\mathbb{R}^k$$ in the way you describe requires the images of all four vertices to be coplanar, forming a square (since the distances between adjacent vertices must be $$1$$ and those between the non-adjacent pairs must be $$\sqrt{2}$$).
Now consider the complete bipartite graph $$K_{2,3}$$. Let us call its vertices $$a_1,a_2,b_1,b_2,b_3$$. In any embedding $$f$$ satisfying your condition, the 4-cycles $$(a_1,b_1,a_2,b_2)$$, $$(a_1,b_1,a_2,b_3)$$ and $$(a_1,b_2,a_2,b_3)$$ would all have to be mapped to squares as above, but the first two of these conditions imply $$f(b_2) = f(b_3)$$, contradiction.