3
$\begingroup$

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.)

Improve this question
$\endgroup$
5
  • $\begingroup$ Are the weights $\omega_{ij}$ undefined when $ij$ is not an edge in $G$? $\endgroup$
    – François G. Dorais
    Commented Apr 26, 2012 at 22:10
  • 3
    $\begingroup$ mathoverflow.net/questions/12394/… mathoverflow.net/questions/7794/… $\endgroup$
    – Gjergji Zaimi
    Commented Apr 26, 2012 at 22:21
  • $\begingroup$ What do you mean with your comment about Kuratowski? Some otherwise planar graphs once given weights will NOT be embeddable faithfully in the plane (take the complete graph on 4 vertices with all weights 1). Or did you simply mean the type of characterisation you were looking for (by forbidden minor, etc...)? $\endgroup$
    – verret
    Commented Apr 26, 2012 at 22:27
  • $\begingroup$ @Francois. I hoped it would be clear from the context: the graph is supposed to be complete, there's supposed to be a - weighted - edge between any two nodes. $\endgroup$
    – Hans-Peter Stricker
    Commented Apr 26, 2012 at 22:30
  • $\begingroup$ @verret. My embeddability criterion is totally different from the one used in defining planarity. My comment about Kuratowski concerns only the two independant ways of characterization. $\endgroup$
    – Hans-Peter Stricker
    Commented Apr 26, 2012 at 22:33

2 Answers 2

Reset to default
3
$\begingroup$

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.

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .