Faithfully embeddable graphs 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.)
 A: To see whether a complete graph (also known as a finite metric space) is isometrically embeddable in $\mathbb{E}^n,$ one needs to check the signs of various minors of the Cayley-Menger matrix, described here.link text This is equivalent to checking whether a certain symmetric matrix $M$ is positive-semi-definite, where, if your graph has $n+1$ vertices $v_0, \dots, v_n,$ the matrix is $n\times n,$ and the entries are given by:
$M_{ii} = d_{0i}^2,$ while $M_{ij} = \frac12 (d_{0i}^2+ d_{0j}^2 - d_{ij}^2).$
The necessity of these conditions is easy, the sufficiency, and more than you ever wanted to know about the subject can be found in Blumenthal's Metric Geometry.
If you are allowed some distortion, you can lower the embedding dimension a lot by using the celebrated Johnson-Lindenstrauss Lemma. Be forewarned that there is an enormous body of work based on this.
A: Perhaps the terminology is misleading: since you are taking the complete graph, it's more of a question about matrices, in my opinion.
Problems of this kind were studied by Neumaier. One paper I found now on his webpage is:
http://solon.cma.univie.ac.at/scan/62.pdf
He gives necessary and sufficient conditions for a given $n \times n$ matrix to be the matrix of squared distances between Euclidean vectors in some $\mathbb{R}^{m}$. The references are also interesting. In particular, in an earlier paper (http://solon.cma.univie.ac.at/scan/16.pdf) he deals with other kinds of spaces too.
