Algorithm for embedding a graph with metric constraints
Let's say the graph is complete, and has weights on edges that satisfy triangle inequality. If you want an isometric embedding (which your original question indicates), then there's a necessary and sufficient characterization: the squares of the distances must be of negative type: specifically, given the $D_{ij} = d^2_{ij}$ values, then they must satisfy the inequality
$$ \sum_{i,j} b_i b_j D_{ij} \le 0, \sum_i b_i = 0$$ for all such $b_i$. All of this is discussed rather well in the book by Deza and Laurent.
It gets really interesting when you allow for some distortion. The special case where G is the complete graph and the weights (while not being constant) satisfy the triangle inequality is the well known metric embedding problem, which has been studied extensively in the theoretical computer science community because of connections to multicommodity flows, and also for data mining problems. A great source is the paper by Linial, London and Rabinovich
Let the distortion be the largest value of $w(x,y)/d(x,y)$ (wlog we can assume the embedding always shrinks distances)
- there's always an embedding into Euclidean space that ensures a distortion $O(\log n)$. The dimension of the space can then be brought down to $O(\log n)$ by applying the Johnson-Lindenstrauss Lemma. This result is due to Bourgain, and the algorithm itself is quite simple: pick $K$ subsets of the input at random, each of size $\log n$, and for each point, let its $i^{th}$ coordinate in the embedding be its distance to the $i^{th}$ such subset. The original proof uses $K = \log^2 n$, and then we use the JL lemma to reduce the dimension back to $\log n$.
1a. this basic construction also works for all $\ell_p$-norms for $1 \le p \le 2$, but the dimensionality reduction of course doesn't.
1b. The construction is tight: the lower bound comes from considering the shortest path metric induced by a constant-degree expander.
The case when you only care to preserve some of the distances is more interesting. While I'm not sure what has been considered for this case, there's another whole body of work that considers the induced shortest path metrics for special graphs (trees, series parallel graphs, planar graphs and so on). One of the most interesting conjectures in this area whether the metric space induced by planar graphs admits a constant-factor distortion embedding into Euclidean space.