This discussion is archived
0 Replies Latest reply: Aug 24, 2009 2:16 AM by 843853 RSS

Dual graph converson from undirected planar graph using Planar face visitor

843853 Newbie
Currently Being Moderated
Hello,

Does anyone know a known algorithm to create the dual graph of a planar graph using planar face visitor? I tried to use a planar face visitor approach. In Boost Library where the development of the graph has been handled mentioned that using an appropriate Planar face visitor one can develop a dual graph from a planar graph. But there is no any more information regarding this. Can someone help me in constructing dual graphs from planar graphs using planar face visitors or using someother algorithm.

Thank you in advance and thanks 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.