Mixing
Algorithm for generating a graph based on a planar graph?
$begingroup$
I have a planar embedding of a graph, $G(V,E)$.
The vertices, $V$, are points in $(x, y)$ space and the edges, $E$, are straight line segments from one vertex to another. Edges do not cross each other, by definition.
What I want to construct is a graph $X$ where the vertices refer to edges in $G$, and nodes in $X$ are adjacent if the corresponding edges in $G$ are adjacent to the face in $G$.
How would I go about constructing this graph given $G$? What would be the algorithm here? Is there a name/term to the kind of graph I am trying to make?
I believe my main bottleneck in figuring this out is that I don't know how to define a "face" properly. I know what a face looks like visually, but not mathematically/algorithmically.
Here's a visual example of what I mean:
The labels a-e refer to edges in $G$ and their corresponding vertices in $X$. The edges $a$ and $e$ are the only edges that aren't adjacent to a common face in $G$. There are only two faces in $G$: the infinite face and the finite one bounded by the triangle $(b, c, d)$.
graph-theory algorithms planar-graph
asked Jan 7 at 17:53
XYZTXYZT
426320
$endgroup$
add a comment |
$begingroup$
I have a planar embedding of a graph, $G(V,E)$.
The vertices, $V$, are points in $(x, y)$ space and the edges, $E$, are straight line segments from one vertex to another. Edges do not cross each other, by definition.
What I want to construct is a graph $X$ where the vertices refer to edges in $G$, and nodes in $X$ are adjacent if the corresponding edges in $G$ are adjacent to the face in $G$.
How would I go about constructing this graph given $G$? What would be the algorithm here? Is there a name/term to the kind of graph I am trying to make?
I believe my main bottleneck in figuring this out is that I don't know how to define a "face" properly. I know what a face looks like visually, but not mathematically/algorithmically.
Here's a visual example of what I mean:
The labels a-e refer to edges in $G$ and their corresponding vertices in $X$. The edges $a$ and $e$ are the only edges that aren't adjacent to a common face in $G$. There are only two faces in $G$: the infinite face and the finite one bounded by the triangle $(b, c, d)$.
graph-theory algorithms planar-graph
asked Jan 7 at 17:53
XYZTXYZT
426320
$endgroup$
add a comment |
$begingroup$
I have a planar embedding of a graph, $G(V,E)$.
The vertices, $V$, are points in $(x, y)$ space and the edges, $E$, are straight line segments from one vertex to another. Edges do not cross each other, by definition.
What I want to construct is a graph $X$ where the vertices refer to edges in $G$, and nodes in $X$ are adjacent if the corresponding edges in $G$ are adjacent to the face in $G$.
How would I go about constructing this graph given $G$? What would be the algorithm here? Is there a name/term to the kind of graph I am trying to make?
I believe my main bottleneck in figuring this out is that I don't know how to define a "face" properly. I know what a face looks like visually, but not mathematically/algorithmically.
Here's a visual example of what I mean:
The labels a-e refer to edges in $G$ and their corresponding vertices in $X$. The edges $a$ and $e$ are the only edges that aren't adjacent to a common face in $G$. There are only two faces in $G$: the infinite face and the finite one bounded by the triangle $(b, c, d)$.
graph-theory algorithms planar-graph
asked Jan 7 at 17:53
XYZTXYZT
426320
$endgroup$
I have a planar embedding of a graph, $G(V,E)$.
The vertices, $V$, are points in $(x, y)$ space and the edges, $E$, are straight line segments from one vertex to another. Edges do not cross each other, by definition.
What I want to construct is a graph $X$ where the vertices refer to edges in $G$, and nodes in $X$ are adjacent if the corresponding edges in $G$ are adjacent to the face in $G$.
How would I go about constructing this graph given $G$? What would be the algorithm here? Is there a name/term to the kind of graph I am trying to make?
I believe my main bottleneck in figuring this out is that I don't know how to define a "face" properly. I know what a face looks like visually, but not mathematically/algorithmically.
Here's a visual example of what I mean:
The labels a-e refer to edges in $G$ and their corresponding vertices in $X$. The edges $a$ and $e$ are the only edges that aren't adjacent to a common face in $G$. There are only two faces in $G$: the infinite face and the finite one bounded by the triangle $(b, c, d)$.
graph-theory algorithms planar-graph
graph-theory algorithms planar-graph
asked Jan 7 at 17:53
XYZTXYZT
426320
asked Jan 7 at 17:53
XYZTXYZT
426320
asked Jan 7 at 17:53
XYZTXYZT
426320
asked Jan 7 at 17:53
XYZTXYZT
426320
asked Jan 7 at 17:53
XYZTXYZT
426320
426320
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
$begingroup$
The graph $X$ you construct this way is the line graph of the dual graph of the original planar embedding.
To construct the graph, it's enough to be able to find faces: given an edge, to list the edges of the two faces on either side of that edge. Then we just do this for all edges to find $X$. How you do this depends on how you store the planar embedding as a data structure.
We might store a planar embedding by specifying the vertex coordinates. Here, the first step should be to sort the edges out of each vertex $v$ by the angle at which they exit $v$. This lets us find the "next edge clockwise out of $v$". Now, given an edge $vw$, we:
- Find the face on one side of $vw$ by taking the edge $wx$ that's next clockwise out of $w$, then taking the edge $xy$ that's next clockwise out of $x$, and so on until we get back to $vw$.
- Find the face on the other side of $vw$ by thinking of the edge as $wv$ and doing the same thing: taking the edge $vu$ that's next clockwise out of $v$, and so on until we get back to $wv$.
Knowing the faces incident to $vw$ tells us all the edges that share a face with $vw$. We can speed things up by remembering the edges on a face the first time we find it; then, when we look at other edges, if they are already in a face we've computed, we don't have to compute that face again.
A slightly more abstract way to store a planar embedding is as a doubly connected edge list. Here, for each edge (represented as a pair of half-edges $vw$ and $wv$) we simply remember the results of the operations we used in the algorithm above: $vw$ has a pointer to $text{next}(vw)$ (the next edge clockwise out of $w$) and to $text{twin}(vw)$ (the reverse edge $wv$). Otherwise, the method is the same.
(Half-edges in a DCEL structure also have a pointer to $text{prev}(vw)$ for convenience: the half-edge $uv$ such that $text{next}(uv) = vw$. We don't use that here, but it's useful in other situations.)
answered Jan 7 at 18:41
Misha LavrovMisha Lavrov
45.7k656107
$endgroup$
$begingroup$
How do you deal with vertices with degree less than 2 when dealing with this? Such as edge a and e in my image in the question.
$endgroup$
– XYZT
Jan 7 at 19:13
$begingroup$
If you have an edge $vw$ and $w$ has degree $1$, then the next edge clockwise out of $w$ is $wv$, because it's the only edge out of $w$. (And in this case, the two faces on either side will just end up being the same face twice, but this is not unique to this situation; it also happens, for example, when $vw$ is a bridge.)
$endgroup$
– Misha Lavrov
Jan 7 at 19:29
$begingroup$
The other weird thing happens when the graph is not connected; in this case, there might be faces which have more than one boundary, and we need to handle them separately.
$endgroup$
– Misha Lavrov
Jan 7 at 19:31
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%2f3065282%2falgorithm-for-generating-a-graph-based-on-a-planar-graph%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
$begingroup$
The graph $X$ you construct this way is the line graph of the dual graph of the original planar embedding.
To construct the graph, it's enough to be able to find faces: given an edge, to list the edges of the two faces on either side of that edge. Then we just do this for all edges to find $X$. How you do this depends on how you store the planar embedding as a data structure.
We might store a planar embedding by specifying the vertex coordinates. Here, the first step should be to sort the edges out of each vertex $v$ by the angle at which they exit $v$. This lets us find the "next edge clockwise out of $v$". Now, given an edge $vw$, we:
- Find the face on one side of $vw$ by taking the edge $wx$ that's next clockwise out of $w$, then taking the edge $xy$ that's next clockwise out of $x$, and so on until we get back to $vw$.
- Find the face on the other side of $vw$ by thinking of the edge as $wv$ and doing the same thing: taking the edge $vu$ that's next clockwise out of $v$, and so on until we get back to $wv$.
Knowing the faces incident to $vw$ tells us all the edges that share a face with $vw$. We can speed things up by remembering the edges on a face the first time we find it; then, when we look at other edges, if they are already in a face we've computed, we don't have to compute that face again.
A slightly more abstract way to store a planar embedding is as a doubly connected edge list. Here, for each edge (represented as a pair of half-edges $vw$ and $wv$) we simply remember the results of the operations we used in the algorithm above: $vw$ has a pointer to $text{next}(vw)$ (the next edge clockwise out of $w$) and to $text{twin}(vw)$ (the reverse edge $wv$). Otherwise, the method is the same.
(Half-edges in a DCEL structure also have a pointer to $text{prev}(vw)$ for convenience: the half-edge $uv$ such that $text{next}(uv) = vw$. We don't use that here, but it's useful in other situations.)
answered Jan 7 at 18:41
Misha LavrovMisha Lavrov
45.7k656107
$endgroup$
$begingroup$
How do you deal with vertices with degree less than 2 when dealing with this? Such as edge a and e in my image in the question.
$endgroup$
– XYZT
Jan 7 at 19:13
$begingroup$
If you have an edge $vw$ and $w$ has degree $1$, then the next edge clockwise out of $w$ is $wv$, because it's the only edge out of $w$. (And in this case, the two faces on either side will just end up being the same face twice, but this is not unique to this situation; it also happens, for example, when $vw$ is a bridge.)
$endgroup$
– Misha Lavrov
Jan 7 at 19:29
$begingroup$
The other weird thing happens when the graph is not connected; in this case, there might be faces which have more than one boundary, and we need to handle them separately.
$endgroup$
– Misha Lavrov
Jan 7 at 19:31
add a comment |
$begingroup$
The graph $X$ you construct this way is the line graph of the dual graph of the original planar embedding.
To construct the graph, it's enough to be able to find faces: given an edge, to list the edges of the two faces on either side of that edge. Then we just do this for all edges to find $X$. How you do this depends on how you store the planar embedding as a data structure.
We might store a planar embedding by specifying the vertex coordinates. Here, the first step should be to sort the edges out of each vertex $v$ by the angle at which they exit $v$. This lets us find the "next edge clockwise out of $v$". Now, given an edge $vw$, we:
- Find the face on one side of $vw$ by taking the edge $wx$ that's next clockwise out of $w$, then taking the edge $xy$ that's next clockwise out of $x$, and so on until we get back to $vw$.
- Find the face on the other side of $vw$ by thinking of the edge as $wv$ and doing the same thing: taking the edge $vu$ that's next clockwise out of $v$, and so on until we get back to $wv$.
Knowing the faces incident to $vw$ tells us all the edges that share a face with $vw$. We can speed things up by remembering the edges on a face the first time we find it; then, when we look at other edges, if they are already in a face we've computed, we don't have to compute that face again.
A slightly more abstract way to store a planar embedding is as a doubly connected edge list. Here, for each edge (represented as a pair of half-edges $vw$ and $wv$) we simply remember the results of the operations we used in the algorithm above: $vw$ has a pointer to $text{next}(vw)$ (the next edge clockwise out of $w$) and to $text{twin}(vw)$ (the reverse edge $wv$). Otherwise, the method is the same.
(Half-edges in a DCEL structure also have a pointer to $text{prev}(vw)$ for convenience: the half-edge $uv$ such that $text{next}(uv) = vw$. We don't use that here, but it's useful in other situations.)
answered Jan 7 at 18:41
Misha LavrovMisha Lavrov
45.7k656107
$endgroup$
$begingroup$
How do you deal with vertices with degree less than 2 when dealing with this? Such as edge a and e in my image in the question.
$endgroup$
– XYZT
Jan 7 at 19:13
$begingroup$
If you have an edge $vw$ and $w$ has degree $1$, then the next edge clockwise out of $w$ is $wv$, because it's the only edge out of $w$. (And in this case, the two faces on either side will just end up being the same face twice, but this is not unique to this situation; it also happens, for example, when $vw$ is a bridge.)
$endgroup$
– Misha Lavrov
Jan 7 at 19:29
$begingroup$
The other weird thing happens when the graph is not connected; in this case, there might be faces which have more than one boundary, and we need to handle them separately.
$endgroup$
– Misha Lavrov
Jan 7 at 19:31
add a comment |
$begingroup$
The graph $X$ you construct this way is the line graph of the dual graph of the original planar embedding.
To construct the graph, it's enough to be able to find faces: given an edge, to list the edges of the two faces on either side of that edge. Then we just do this for all edges to find $X$. How you do this depends on how you store the planar embedding as a data structure.
We might store a planar embedding by specifying the vertex coordinates. Here, the first step should be to sort the edges out of each vertex $v$ by the angle at which they exit $v$. This lets us find the "next edge clockwise out of $v$". Now, given an edge $vw$, we:
- Find the face on one side of $vw$ by taking the edge $wx$ that's next clockwise out of $w$, then taking the edge $xy$ that's next clockwise out of $x$, and so on until we get back to $vw$.
- Find the face on the other side of $vw$ by thinking of the edge as $wv$ and doing the same thing: taking the edge $vu$ that's next clockwise out of $v$, and so on until we get back to $wv$.
Knowing the faces incident to $vw$ tells us all the edges that share a face with $vw$. We can speed things up by remembering the edges on a face the first time we find it; then, when we look at other edges, if they are already in a face we've computed, we don't have to compute that face again.
A slightly more abstract way to store a planar embedding is as a doubly connected edge list. Here, for each edge (represented as a pair of half-edges $vw$ and $wv$) we simply remember the results of the operations we used in the algorithm above: $vw$ has a pointer to $text{next}(vw)$ (the next edge clockwise out of $w$) and to $text{twin}(vw)$ (the reverse edge $wv$). Otherwise, the method is the same.
(Half-edges in a DCEL structure also have a pointer to $text{prev}(vw)$ for convenience: the half-edge $uv$ such that $text{next}(uv) = vw$. We don't use that here, but it's useful in other situations.)
answered Jan 7 at 18:41
Misha LavrovMisha Lavrov
45.7k656107
$endgroup$
The graph $X$ you construct this way is the line graph of the dual graph of the original planar embedding.
To construct the graph, it's enough to be able to find faces: given an edge, to list the edges of the two faces on either side of that edge. Then we just do this for all edges to find $X$. How you do this depends on how you store the planar embedding as a data structure.
We might store a planar embedding by specifying the vertex coordinates. Here, the first step should be to sort the edges out of each vertex $v$ by the angle at which they exit $v$. This lets us find the "next edge clockwise out of $v$". Now, given an edge $vw$, we:
- Find the face on one side of $vw$ by taking the edge $wx$ that's next clockwise out of $w$, then taking the edge $xy$ that's next clockwise out of $x$, and so on until we get back to $vw$.
- Find the face on the other side of $vw$ by thinking of the edge as $wv$ and doing the same thing: taking the edge $vu$ that's next clockwise out of $v$, and so on until we get back to $wv$.
Knowing the faces incident to $vw$ tells us all the edges that share a face with $vw$. We can speed things up by remembering the edges on a face the first time we find it; then, when we look at other edges, if they are already in a face we've computed, we don't have to compute that face again.
A slightly more abstract way to store a planar embedding is as a doubly connected edge list. Here, for each edge (represented as a pair of half-edges $vw$ and $wv$) we simply remember the results of the operations we used in the algorithm above: $vw$ has a pointer to $text{next}(vw)$ (the next edge clockwise out of $w$) and to $text{twin}(vw)$ (the reverse edge $wv$). Otherwise, the method is the same.
(Half-edges in a DCEL structure also have a pointer to $text{prev}(vw)$ for convenience: the half-edge $uv$ such that $text{next}(uv) = vw$. We don't use that here, but it's useful in other situations.)
answered Jan 7 at 18:41
Misha LavrovMisha Lavrov
45.7k656107
answered Jan 7 at 18:41
Misha LavrovMisha Lavrov
45.7k656107
answered Jan 7 at 18:41
Misha LavrovMisha Lavrov
45.7k656107
answered Jan 7 at 18:41
Misha LavrovMisha Lavrov
45.7k656107
45.7k656107
$begingroup$
How do you deal with vertices with degree less than 2 when dealing with this? Such as edge a and e in my image in the question.
$endgroup$
– XYZT
Jan 7 at 19:13
$begingroup$
If you have an edge $vw$ and $w$ has degree $1$, then the next edge clockwise out of $w$ is $wv$, because it's the only edge out of $w$. (And in this case, the two faces on either side will just end up being the same face twice, but this is not unique to this situation; it also happens, for example, when $vw$ is a bridge.)
$endgroup$
– Misha Lavrov
Jan 7 at 19:29
$begingroup$
The other weird thing happens when the graph is not connected; in this case, there might be faces which have more than one boundary, and we need to handle them separately.
$endgroup$
– Misha Lavrov
Jan 7 at 19:31
add a comment |
$begingroup$
How do you deal with vertices with degree less than 2 when dealing with this? Such as edge a and e in my image in the question.
$endgroup$
– XYZT
Jan 7 at 19:13
$begingroup$
If you have an edge $vw$ and $w$ has degree $1$, then the next edge clockwise out of $w$ is $wv$, because it's the only edge out of $w$. (And in this case, the two faces on either side will just end up being the same face twice, but this is not unique to this situation; it also happens, for example, when $vw$ is a bridge.)
$endgroup$
– Misha Lavrov
Jan 7 at 19:29
$begingroup$
The other weird thing happens when the graph is not connected; in this case, there might be faces which have more than one boundary, and we need to handle them separately.
$endgroup$
– Misha Lavrov
Jan 7 at 19:31
$begingroup$
How do you deal with vertices with degree less than 2 when dealing with this? Such as edge a and e in my image in the question.
$endgroup$
– XYZT
Jan 7 at 19:13
$begingroup$
How do you deal with vertices with degree less than 2 when dealing with this? Such as edge a and e in my image in the question.
$endgroup$
– XYZT
Jan 7 at 19:13
$begingroup$
If you have an edge $vw$ and $w$ has degree $1$, then the next edge clockwise out of $w$ is $wv$, because it's the only edge out of $w$. (And in this case, the two faces on either side will just end up being the same face twice, but this is not unique to this situation; it also happens, for example, when $vw$ is a bridge.)
$endgroup$
– Misha Lavrov
Jan 7 at 19:29
$begingroup$
If you have an edge $vw$ and $w$ has degree $1$, then the next edge clockwise out of $w$ is $wv$, because it's the only edge out of $w$. (And in this case, the two faces on either side will just end up being the same face twice, but this is not unique to this situation; it also happens, for example, when $vw$ is a bridge.)
$endgroup$
– Misha Lavrov
Jan 7 at 19:29
$begingroup$
The other weird thing happens when the graph is not connected; in this case, there might be faces which have more than one boundary, and we need to handle them separately.
$endgroup$
– Misha Lavrov
Jan 7 at 19:31
$begingroup$
The other weird thing happens when the graph is not connected; in this case, there might be faces which have more than one boundary, and we need to handle them separately.
$endgroup$
– Misha Lavrov
Jan 7 at 19:31
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%2f3065282%2falgorithm-for-generating-a-graph-based-on-a-planar-graph%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
