Mixing
Proof that geodesic distance is related to Euclidean distance between two vertices in a Tutte embedding?
up vote
0
down vote
favorite
Say we have a Tutte embedding of a planar graph (that is, a graph whose positions in a plane are determined by 1. a set of outer vertices and 2. the rule that each interior vertex's position is the average of its geodesic neighbors'). If we choose any vertex $v_0$ in the interior of the embedding and another vertex $v_n$ whose geodesic distance (i.e. shortest path in terms of number of edges or hop count) from $v_0$ is $n$, does there exist some vertex $v_{n-1}$ located on one of the geodesic shortest paths to $v_n$ but at geodesic distance $n-1$ relative to $v_0$ that is also closer to $v_0$ in Euclidean distance?
My intuition suggests that this property is true looking at any Tutte embedding, but I am having difficulty nailing this all down as a proof and have not found any explicit explanation along these lines in the literature.
My progress so far has been realizing that anytime one tries to place a $v_n$ vertex closer to $v_0$ in Euclidean distance than $v_{n-1}$ this seems to create a concave structure, violating a basic property of the Tutte embedding. However I am not certain how to generalize beyond specific scenarios - it seems like some kind of inductive proof would be needed. Another observation is that the contours formed by connecting the points of a fixed geodesic distance around $v_0$ seem to never cross each other, instead forming beautiful concentric polygons.
The context of the problem is that I want to be able to make a mathematically grounded statement regarding what one can say about the Euclidean spatial relations of vertices given only topological/graph connectivity and stipulation that they lie in a Tutte embedding. As my title suggests, other proofs that accomplish this are also of interest to me.
In the attached image, I have identified some example origin points $v_0$ and drawn geodesic distance contours $n=1, 2$ around the two example points. The arrows indicate my attempt to locate points that break the rule, but in fact they never do - always a $v_n$ point is further away from $v_0$ in Euclidean distance than some point $v_{n-1}$ on the path even if not all.
Hope it is all clear, and thanks for your help.
Example Tutte Embedding with Reference Points and Geodesic Distance Denoted
measure-theory graph-theory euclidean-geometry
asked 2 days ago
Entangler
11
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
0
down vote
favorite
Say we have a Tutte embedding of a planar graph (that is, a graph whose positions in a plane are determined by 1. a set of outer vertices and 2. the rule that each interior vertex's position is the average of its geodesic neighbors'). If we choose any vertex $v_0$ in the interior of the embedding and another vertex $v_n$ whose geodesic distance (i.e. shortest path in terms of number of edges or hop count) from $v_0$ is $n$, does there exist some vertex $v_{n-1}$ located on one of the geodesic shortest paths to $v_n$ but at geodesic distance $n-1$ relative to $v_0$ that is also closer to $v_0$ in Euclidean distance?
My intuition suggests that this property is true looking at any Tutte embedding, but I am having difficulty nailing this all down as a proof and have not found any explicit explanation along these lines in the literature.
My progress so far has been realizing that anytime one tries to place a $v_n$ vertex closer to $v_0$ in Euclidean distance than $v_{n-1}$ this seems to create a concave structure, violating a basic property of the Tutte embedding. However I am not certain how to generalize beyond specific scenarios - it seems like some kind of inductive proof would be needed. Another observation is that the contours formed by connecting the points of a fixed geodesic distance around $v_0$ seem to never cross each other, instead forming beautiful concentric polygons.
The context of the problem is that I want to be able to make a mathematically grounded statement regarding what one can say about the Euclidean spatial relations of vertices given only topological/graph connectivity and stipulation that they lie in a Tutte embedding. As my title suggests, other proofs that accomplish this are also of interest to me.
In the attached image, I have identified some example origin points $v_0$ and drawn geodesic distance contours $n=1, 2$ around the two example points. The arrows indicate my attempt to locate points that break the rule, but in fact they never do - always a $v_n$ point is further away from $v_0$ in Euclidean distance than some point $v_{n-1}$ on the path even if not all.
Hope it is all clear, and thanks for your help.
Example Tutte Embedding with Reference Points and Geodesic Distance Denoted
measure-theory graph-theory euclidean-geometry
asked 2 days ago
Entangler
11
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
up vote
0
down vote
favorite
up vote
0
down vote
favorite
Say we have a Tutte embedding of a planar graph (that is, a graph whose positions in a plane are determined by 1. a set of outer vertices and 2. the rule that each interior vertex's position is the average of its geodesic neighbors'). If we choose any vertex $v_0$ in the interior of the embedding and another vertex $v_n$ whose geodesic distance (i.e. shortest path in terms of number of edges or hop count) from $v_0$ is $n$, does there exist some vertex $v_{n-1}$ located on one of the geodesic shortest paths to $v_n$ but at geodesic distance $n-1$ relative to $v_0$ that is also closer to $v_0$ in Euclidean distance?
My intuition suggests that this property is true looking at any Tutte embedding, but I am having difficulty nailing this all down as a proof and have not found any explicit explanation along these lines in the literature.
My progress so far has been realizing that anytime one tries to place a $v_n$ vertex closer to $v_0$ in Euclidean distance than $v_{n-1}$ this seems to create a concave structure, violating a basic property of the Tutte embedding. However I am not certain how to generalize beyond specific scenarios - it seems like some kind of inductive proof would be needed. Another observation is that the contours formed by connecting the points of a fixed geodesic distance around $v_0$ seem to never cross each other, instead forming beautiful concentric polygons.
The context of the problem is that I want to be able to make a mathematically grounded statement regarding what one can say about the Euclidean spatial relations of vertices given only topological/graph connectivity and stipulation that they lie in a Tutte embedding. As my title suggests, other proofs that accomplish this are also of interest to me.
In the attached image, I have identified some example origin points $v_0$ and drawn geodesic distance contours $n=1, 2$ around the two example points. The arrows indicate my attempt to locate points that break the rule, but in fact they never do - always a $v_n$ point is further away from $v_0$ in Euclidean distance than some point $v_{n-1}$ on the path even if not all.
Hope it is all clear, and thanks for your help.
Example Tutte Embedding with Reference Points and Geodesic Distance Denoted
measure-theory graph-theory euclidean-geometry
asked 2 days ago
Entangler
11
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Say we have a Tutte embedding of a planar graph (that is, a graph whose positions in a plane are determined by 1. a set of outer vertices and 2. the rule that each interior vertex's position is the average of its geodesic neighbors'). If we choose any vertex $v_0$ in the interior of the embedding and another vertex $v_n$ whose geodesic distance (i.e. shortest path in terms of number of edges or hop count) from $v_0$ is $n$, does there exist some vertex $v_{n-1}$ located on one of the geodesic shortest paths to $v_n$ but at geodesic distance $n-1$ relative to $v_0$ that is also closer to $v_0$ in Euclidean distance?
My intuition suggests that this property is true looking at any Tutte embedding, but I am having difficulty nailing this all down as a proof and have not found any explicit explanation along these lines in the literature.
My progress so far has been realizing that anytime one tries to place a $v_n$ vertex closer to $v_0$ in Euclidean distance than $v_{n-1}$ this seems to create a concave structure, violating a basic property of the Tutte embedding. However I am not certain how to generalize beyond specific scenarios - it seems like some kind of inductive proof would be needed. Another observation is that the contours formed by connecting the points of a fixed geodesic distance around $v_0$ seem to never cross each other, instead forming beautiful concentric polygons.
The context of the problem is that I want to be able to make a mathematically grounded statement regarding what one can say about the Euclidean spatial relations of vertices given only topological/graph connectivity and stipulation that they lie in a Tutte embedding. As my title suggests, other proofs that accomplish this are also of interest to me.
In the attached image, I have identified some example origin points $v_0$ and drawn geodesic distance contours $n=1, 2$ around the two example points. The arrows indicate my attempt to locate points that break the rule, but in fact they never do - always a $v_n$ point is further away from $v_0$ in Euclidean distance than some point $v_{n-1}$ on the path even if not all.
Hope it is all clear, and thanks for your help.
Example Tutte Embedding with Reference Points and Geodesic Distance Denoted
measure-theory graph-theory euclidean-geometry
measure-theory graph-theory euclidean-geometry
asked 2 days ago
Entangler
11
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
Entangler
11
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
edited 2 hours ago
asked 2 days ago
Entangler
11
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
asked 2 days ago
Entangler
11
asked 2 days ago
Entangler
11
11
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
New contributor
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
Entangler is a new contributor to this site. Take care in asking for clarification, commenting, and answering.
Check out our Code of Conduct.
add a comment |
add a comment |
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
active
oldest
votes
Entangler is a new contributor. Be nice, and check out our Code of Conduct.
Entangler is a new contributor. Be nice, and check out our Code of Conduct.
Entangler is a new contributor. Be nice, and check out our Code of Conduct.
Entangler is a new contributor. Be nice, and check out our Code of Conduct.
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%2f3001201%2fproof-that-geodesic-distance-is-related-to-euclidean-distance-between-two-vertic%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
