Consider a weighted graph $G$ with weights $\omega_{ii}=0$, $\omega_{ij}=\omega_{ji}>0$, obeying the triangle inequality. One might want to ask into which metric spaces $X$ such a graph can be embedded **faithfully**, i.e. such that the (abstract) *weight* $\omega_{ij}$ between two vertices equals their (geometric) *distance* $d_{ij}$.

One trivial answer is: into the graph $G$ itself which is by definition a metric space. But this is not what one wants to get as an answer. Neither is - in the case of a graph with $n$ vertices - an answer like *some distortion of* $\mathbb{R}^{n-1}$.

So what would be - if any - a sensible family of metric spaces one could restrict this question to in order to get interesting answers?

To turn the problem around:

Given a metric space $X$ and the family of graphs that can be embedded faithfully into $X$. Can these graphs be characterized otherwise, eventually?

(Think of Kuratowski's characterization of planar graphs.)