When can a weighted graph be embedded in a metric space?
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?
graph-theory metric-spaces
edited Jan 4 at 21:23
amWhy
192k28225439
asked Jan 4 at 21:07
theQmantheQman
42228
add a comment |
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?
graph-theory metric-spaces
edited Jan 4 at 21:23
amWhy
192k28225439
asked Jan 4 at 21:07
theQmantheQman
42228
If you have a complete graph this is easy, since there is always a unique triangle with a given set of side lengths.
– SmileyCraft
Jan 4 at 21:13
But what if the weights (i.e. distances) are already provided? Surely not every set of weights can be consistent with a metric?
– theQman
Jan 4 at 21:15
Well you can iteratively make an embedding, embedding one point at a time, until you either embedded all points or run into a contradiction.
– SmileyCraft
Jan 4 at 21:17
@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.
– Not Mike
Jan 4 at 21:34
add a comment |
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?
graph-theory metric-spaces
edited Jan 4 at 21:23
amWhy
192k28225439
asked Jan 4 at 21:07
theQmantheQman
42228
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?
graph-theory metric-spaces
graph-theory metric-spaces
edited Jan 4 at 21:23
amWhy
192k28225439
asked Jan 4 at 21:07
theQmantheQman
42228
edited Jan 4 at 21:23
amWhy
192k28225439
asked Jan 4 at 21:07
theQmantheQman
42228
edited Jan 4 at 21:23
amWhy
192k28225439
edited Jan 4 at 21:23
amWhy
192k28225439
edited Jan 4 at 21:23
amWhy
192k28225439
192k28225439
asked Jan 4 at 21:07
theQmantheQman
42228
asked Jan 4 at 21:07
theQmantheQman
42228
asked Jan 4 at 21:07
theQmantheQman
42228
42228
If you have a complete graph this is easy, since there is always a unique triangle with a given set of side lengths.
– SmileyCraft
Jan 4 at 21:13
But what if the weights (i.e. distances) are already provided? Surely not every set of weights can be consistent with a metric?
– theQman
Jan 4 at 21:15
Well you can iteratively make an embedding, embedding one point at a time, until you either embedded all points or run into a contradiction.
– SmileyCraft
Jan 4 at 21:17
@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.
– Not Mike
Jan 4 at 21:34
add a comment |
If you have a complete graph this is easy, since there is always a unique triangle with a given set of side lengths.
– SmileyCraft
Jan 4 at 21:13
But what if the weights (i.e. distances) are already provided? Surely not every set of weights can be consistent with a metric?
– theQman
Jan 4 at 21:15
Well you can iteratively make an embedding, embedding one point at a time, until you either embedded all points or run into a contradiction.
– SmileyCraft
Jan 4 at 21:17
@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.
– Not Mike
Jan 4 at 21:34
If you have a complete graph this is easy, since there is always a unique triangle with a given set of side lengths.
– SmileyCraft
Jan 4 at 21:13
If you have a complete graph this is easy, since there is always a unique triangle with a given set of side lengths.
– SmileyCraft
Jan 4 at 21:13
But what if the weights (i.e. distances) are already provided? Surely not every set of weights can be consistent with a metric?
– theQman
Jan 4 at 21:15
But what if the weights (i.e. distances) are already provided? Surely not every set of weights can be consistent with a metric?
– theQman
Jan 4 at 21:15
Well you can iteratively make an embedding, embedding one point at a time, until you either embedded all points or run into a contradiction.
– SmileyCraft
Jan 4 at 21:17
Well you can iteratively make an embedding, embedding one point at a time, until you either embedded all points or run into a contradiction.
– SmileyCraft
Jan 4 at 21:17
@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.
– Not Mike
Jan 4 at 21:34
@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.
– Not Mike
Jan 4 at 21:34
add a comment |
2 Answers
2
active
oldest
votes
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.
answered Jan 4 at 21:51
jmerryjmerry
2,884312
add a comment |
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.
answered Jan 4 at 22:42
freehumoristfreehumorist
158112
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062113%2fwhen-can-a-weighted-graph-be-embedded-in-a-metric-space%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
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.
answered Jan 4 at 21:51
jmerryjmerry
2,884312
add a comment |
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.
answered Jan 4 at 21:51
jmerryjmerry
2,884312
add a comment |
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.
answered Jan 4 at 21:51
jmerryjmerry
2,884312
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.
answered Jan 4 at 21:51
jmerryjmerry
2,884312
answered Jan 4 at 21:51
jmerryjmerry
2,884312
answered Jan 4 at 21:51
jmerryjmerry
2,884312
answered Jan 4 at 21:51
jmerryjmerry
2,884312
2,884312
add a comment |
add a comment |
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.
answered Jan 4 at 22:42
freehumoristfreehumorist
158112
add a comment |
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.
answered Jan 4 at 22:42
freehumoristfreehumorist
158112
add a comment |
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.
answered Jan 4 at 22:42
freehumoristfreehumorist
158112
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.
answered Jan 4 at 22:42
freehumoristfreehumorist
158112
answered Jan 4 at 22:42
freehumoristfreehumorist
158112
answered Jan 4 at 22:42
freehumoristfreehumorist
158112
answered Jan 4 at 22:42
freehumoristfreehumorist
158112
158112
add a comment |
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3062113%2fwhen-can-a-weighted-graph-be-embedded-in-a-metric-space%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
If you have a complete graph this is easy, since there is always a unique triangle with a given set of side lengths.
– SmileyCraft
Jan 4 at 21:13
But what if the weights (i.e. distances) are already provided? Surely not every set of weights can be consistent with a metric?
– theQman
Jan 4 at 21:15
Well you can iteratively make an embedding, embedding one point at a time, until you either embedded all points or run into a contradiction.
– SmileyCraft
Jan 4 at 21:17
@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.
– Not Mike
Jan 4 at 21:34