Given a graph $G = (V, E)$, I want to embed it into a $n$-dimensional space $\mathbb{R}^n$, while respecting the following conditions:
Let $x_i$ be the $n$-dimensional embedding of vertex $v_i$.
- If $e_{ij} \in E$ (there exists an edge between $v_i$ and $v_j$) then $||x_i – x_j|| \le \epsilon$
- If $e_{ij} \notin E$, then $||x_i – x_j|| \gt \epsilon$
Can such an embedding exist for a certain $n$ for any graph? If yes, could you point me towards some relevant theory? I am particularly interested in lower bounds for $n$ with respect to characteristics of the graph, such as degree, $|V|$, $|E|$, etc. If not, are there some conditions on the graph structure under which such an embedding can exist?
Note: this looks similar to the concept of dimension of a graph, which is the value of $n$ for which an embedding exists such that all edges have length 1. However, the concept of dimension does not require vertices that are not connected to have distance > 1, which violates my requirement 2.
Best Answer
The notion you're looking for is the sphericity of a graph, which is defined as the smallest $n$ for which there is an embedding in $\mathbb{R}^n$ with the properties you describe. Let me denote the sphericity of $G = (V,E)$ by $sph(G)$. It is not difficult to show that $sph(G) \leq |V|$ (essentially you take the $|V|$-dimensional simplex and perturb the vertices suitably), and with a bit more work one can show that $sph(G) \leq |V| - 1$. The most attractive lower bound I have found is in Section 5.4 of this paper, where it is shown that $$ sph(G) \geq \frac{\log\alpha(G)}{\log(2r(G)+1)},$$
where $\alpha(G)$ and $r(G)$ are the independence number and radius of $G$, respectively.