Dual graph algorithm
Hello to all of you!
Does anyone know a known algorithm to create the dual graph of a planar (undirected) graph? Or could you give me a hint? I tried to devise a DFS approach, which would use the back and cross edges of the DFS tree in order to form the faces. The problem is that I need the set of disjoint minimum cycles. Thus I would need an algorithm to calculate the difference AUB - A^B, for two cycles A,B, where B is a part of A. By the way, is there any recommended representation of a face?
Thank you in advance and thaks for your time!
P.S. For those who would ask what is a face, a face is the area defined by a minimum cycle e.g.:
In this mesh (ignore dots):
a-b-c
I . I . I
d-e-f
a,b,c,d form a face
b,c,e,f form a face
and there is also the external face -which by the way how can it be defined?
P.S.2 the Dual Graph is the graph formed by representing each face as a node and each edge which separates two faces, as an edge between the two newlly created nodes.
[1051 byte] By [
M.M.a] at [2007-10-3 5:41:44]
> Does anyone know a known algorithm to create the dual graph of a planar (undirected) graph?You phrase that as though dual graphs were unique. They aren't. Your first step probably needs to be embedding the graph in the plane.
YAT beat me too it while I was drawing pictures.
B C
/ ||
A||
\ ||
D--E
B C
| \|
| A |
| /|
D--E
Planar means can be embedded, it does not need to be unique. Different embeddings would have different faces and therefor different duals.
OK , guess you're right! Since the following graph:
OO
|\/|
| \ / |
| O |
| / \ |
|/\|
OO
and this one
O
|\
| O |
| | \|
| | O
| | /|
| O |
|/
O
are the same, however they have a different embedding AND dual graph.
So, the embedding is defined by the coordinates of the nodes, along with
their connectivity info.
This means that for a start I need an algorithm to return the different faces of
the graph. (at least these ones have to be fixed in number -no?). Then from
the topological information for each face I should check their neighboring
relations.
For the face discovery I have thought of the following algorithm (in language):
Create the DFS tree
-Start from the root r of the DFS tree and visit each neighboring node based
on the preordering number
-When we reach a node b which has one or more back-edges we have a
cycle.
--For each back edge we go back to the node bs, starting from the
back-edge which leads us to the node bs with the greatest start time
(gretest preorder number).
--from this node, bs, visit neighboring nodes, again based on preordering,
until we find the node b (which will complete the cycle)
While going towards b follow in reverse direction, each backedge that
terminates a currntly visited node, and starts from a node t whose
preorder[t] <= preorder[b] (to avoid bypassing b by going deeper in the tree)
and
postorder[t] > postorder[b] (to avoid reaching another branch)
-When we reach a node, cs,which has a cross edge to another node, ce, of
the DFS tree (as a cross edge I mean a (u,v) where pre[u]>pre[v] and
post[u]>post[v]) we have found another cycle, thus a face
--from ce we go up the DFS, i.e., in reverse preordering, until we find a node
a whose postorder[a] > post[cs]
--from a we go down the DFS (in preordering) choosing the neighbor, an,
whose postorder[an] >= postorder[cs] (equality means we have found cs
thus we're done). While descending we follow the same rules as before, in
the case of the back edge.
Of course the implementation of this algorithms has to support two-way movement in the DFS tree. The distinction between tree,back and cross edges is made through the pre and post ordering.
I'm not sure but i think that, with the restrictions I have put, this algorithm can be ran while discovering and creating the DFS tree, rather after the DFS tree has been fully created.
So if the algorithm IS correct, I only need a way to derive the connectivity between the produced faces via their topological information. That is, apart from the indisputable fact that if two faces have two nodes in common, they are neighbors, we have to locate all other edges between faces.
One idea is for each pair of faces to check their min and max, X and Y coordinates. I have a sense that for faces f1and f2 where,
f1_max_X > f2_max_X and
f1_min_X < f2_min_X and
f1_max_Y > f2_max_Y and
f1_min_Y < f2_min_Y
(there must be at most one equality (i.e. <=)but I guess its no harm to add all equalities there)
holds, f1 and f2 are neighbors, thus an edge (f1,f2) must exist in the dual graph.
Of course I have written a lot but I really would like to know if there's a "good" algortihm to create faces out there and a technique to create edges between faces given the coordinates.
I propose the ideas in case someone finds something wrong and reports it or otherwise someone else finds my answer useful in the same topic.
Thank you in advance!
Message was edited by:
M.M.
M.M.a at 2007-7-14 23:49:38 >
You've got an embedding, use it!
The first step is correct, you need a spanning tree, but it can be any spanning tree, not necessarily the one a DFS gives you. Each edge not in the tree seperates the plane, (i.e. creates a face). So you have a starting point for each face.
The next question is how to find the remaining edges in each face. Imagine you're blind, and you're standing in one of the faces. To find the rest of the walls of the face, put your hand against the wall and start walking. If something gets in your way, turn. You'll probably want to mark each wall with some secret Braille codes so you know which ones you've seen. Each wall has two sides, so if you start tracing on one side of the wall and you find some Braille, you need to go to the other side. The geometrical information from your embedding will help you to complete this step.
Good luck.
Mmm.... I was sure I had heard this solution in the past. E.g. always take the first edge you meet in the clockwise direction for each visited node, or smthg. The problem is I couldn't define the first edge, or more importantly, were to start from. Should I start using the equation of the line x=C and then start turning this line at an angle a and checking which edge will terminate at a coordinate over the line y=cos(a) * (x + C) ? I guess somthing like this would do, but there are a lot of questions like how much should I increase the angle a each time and so on....
On the other hand, taking the X=Xo from the current node and checking which neighbor, i, forms the Yi=cos(a)*(Xi + Xo) with the lowest positive a, might give a better asolution. But is it the best?
Another question is whether I should do this for every node of the spanning tree. I guess so, if I want to find every face. I wonder if this covers your comment:
>if you start
> tracing on one side of the wall and you find some
> Braille, you need to go to the other side. The
> geometrical information from your embedding will help
> you to complete this step.
Thank you very much for your time!
P.S. Its too bad I lost my notes (can't find them 2 days now), or I wouldn't waste your time :) - thanks again!
M.M.a at 2007-7-14 23:49:38 >
> Mmm.... I was sure I had heard this solution in the
> past. E.g. always take the first edge you meet in the
> clockwise direction for each visited node, or smthg.
> The problem is I couldn't define the first edge, or
> more importantly, were to start from. Should I start
> using the equation of the line x=C and then start
> turning this line at an angle a and checking which
> edge will terminate at a coordinate over the line
> y=cos(a) * (x + C) ? I guess somthing like this
> would do, but there are a lot of questions like how
> much should I increase the angle a each time and so
> on....
> On the other hand, taking the X=Xo from the current
> node and checking which neighbor, i, forms the
> Yi=cos(a)*(Xi + Xo) with the lowest positive a, might
> give a better asolution. But is it the best?
Well, you want the edge that forms the most acute angle with the edge you're tracing. The trigonometry shouldn't be that difficult to work out, though I don't have time for it now.
> Another question is whether I should do this for
> every node of the spanning tree. I guess so, if I
> want to find every face. I wonder if this covers your
> comment:
Not every node of the spanning tree. You start tracing with each edge that's not in the spanning tree. There are two sides to each edge, and you'll need to trace both sides to find all the faces. The marking step is just to make sure you don't trace the same face twice.
For once more, thank you!
I finally found my notes and saw that one thing to help me with the face detection is to have constructed the adjacency list puting adjacent nodes in counter clock wise order. This way, after detecting a face, I can go to the next unchecked edge via the next counter clock wise node to form that edge.
Anyway, maybe this is too much of detail. I also saw that in order to represent the faces I should record ajacent edges and not adjacent nodes.
Thanks again!
M.M.a at 2007-7-14 23:49:38 >
