4
$\begingroup$

If you have $n$ points in $\mathbf{R}^2$, and you write down the $n \times n$ matrix of distances between each pair of points, then you get a weighted graph with $n$ nodes.

When can you do the reverse? I.e., when can the nodes in a weighted graph be embedded in some metric space? Is there some simple characterization? Has this been studied before?

$\endgroup$
5
  • 1
    $\begingroup$ If you have a complete graph this is easy, since there is always a unique triangle with a given set of side lengths. $\endgroup$ Jan 4, 2019 at 21:13
  • $\begingroup$ But what if the weights (i.e. distances) are already provided? Surely not every set of weights can be consistent with a metric? $\endgroup$
    – theQman
    Jan 4, 2019 at 21:15
  • $\begingroup$ Well you can iteratively make an embedding, embedding one point at a time, until you either embedded all points or run into a contradiction. $\endgroup$ Jan 4, 2019 at 21:17
  • $\begingroup$ @theQman you are correct that this is not always possible when given the weights in advance; even when the assignment of weights serves as a metric on the graph. $\endgroup$
    – Not Mike
    Jan 4, 2019 at 21:34
  • $\begingroup$ Related question: Determine if a weighted graph can be physically constructed, treating weight as Euclidean distance (ie check if subset of distances are consistent) which links to some other related questions $\endgroup$
    – Silverfish
    Sep 17, 2022 at 17:36

3 Answers 3

3
$\begingroup$

An obvious necessary conditions are non-negativity of weights and that in each cycle the weight of the longest side is not bigger than the sum of the other edges. This condition also is sufficient, because if it is satisfied then we can consider the vertices of the graph as points of a metric space $(X,d)$ with the distance $d(x,y)$ equal to the minimum weight of a path between $x$ and $y$ for each $x,y\in X$. (The second condition assures that $d(x,y)$ is the weight of and edge between $x$ and $y$ for any adjacent vertices $x$ and $y$ of the graph).

$\endgroup$
3
  • 1
    $\begingroup$ Nice answer! Corollary: A nonnegatively weighted acyclic graph is a metric space! $\endgroup$
    – dohmatob
    May 20, 2020 at 10:25
  • 1
    $\begingroup$ @dohmatob Saying more rigorously, it can be embedded in a metric space. $\endgroup$ May 20, 2020 at 16:16
  • $\begingroup$ Sure, that is what i meant by "is a" ;) $\endgroup$
    – dohmatob
    May 20, 2020 at 16:17
1
$\begingroup$

There's definitely no simple answer. We have obvious restrictions (by the triangle inequality, the length of any path from $A$ to $B$ is greater than or equal to the length of the direct edge) and dimension-linked restrictions (e.g, we can't fit a $K_4$ with all edges equal in two dimensions), but we also have less obvious restrictions - for example, a $K_4$ with edges $AB=AC=AD=BC=BD=1$ and $CD=1.8$ is impossible in any Euclidean space. That example is a special case of a restriction we get from the formula for the volume of a tetrahedron in terms of its edges: $AB^2+CD^2 \le AC^2+BD^2+BC^2+AD^2$ because the square of the volume is nonnegative.

In the case of all (included) edges marked at length $1$ and restricted to the Euclidean plane, these are known as unit-distance graphs. My avatar is an example of such - a Petersen graph drawn with all edges of equal length.

$\endgroup$
0
$\begingroup$

In such a Matrix, notice that we'll have always the diagonal zero and the triangularity would be symmetrical with diagonal as axis. It's better to keep it on mind. Because, the information we are interested into would already be contained in one of the superior/inferior triangular sides independently.

The reason I precised the detail above is that my following suggestion came to my mind while I was working on Matrix. If we take a break from math and raise our head, the viewpoint as we see the paper on which the Matrix is written can help: We can take the usual Euclidean distance between "indices in the Matrix," rather than diving into $\mathbb{R}^2$ space of the question.

The relation above will be: a surjective distance function; a metric independent of the graph's parameter which restricts the reversibility of the graph's embedding.

$\endgroup$

You must log in to answer this question.

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