Graph theory
in [Math]
|
Prev: TWO BILLION ABSOLUTLY CORRECT PLACED PRIME NUMBERS FROM HOPE RESEARCH
Next: ? determining the number of zeros of given eqns
From: Rolf Wester on 25 May 2010 08:01 Hi, I would like to determine the edges belonging to the faces of a planar graph given the vertexes and their corresponding neighbors. For the case that all faces are triangles I have found a simple algorithm but I have no idea how to do it in case of 4 or more edges. Is there any algorithm for this problem? Many thanks in advance Rolf
From: Chip Eastham on 25 May 2010 09:49 On May 25, 8:01 am, Rolf Wester <rolf.wes...(a)ilt.fraunhofer.de> wrote: > Hi, > > I would like to determine the edges belonging to the faces of a planar graph given the vertexes and their corresponding neighbors. > For the case that all faces are triangles I have found a simple algorithm but I have no idea how to do it in case of 4 or more edges. > Is there any algorithm for this problem? > > Many thanks in advance > > Rolf Hi, Rolf: You may be interested in the Boost Graph Library approach: [Planar Face Traversal -- Boost Graph Library] http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/planar_face_traversal.html If the planar graph is biconnected, and we include the "unbounded" face, then each edge belongs to exactly two faces, each vertex belongs to as many faces as its degree, and given the number of edges and vertices, the number of faces can be computed from Euler's formula. If not biconnected, you may want to (repeatedly) trim away vertices of degree one until only "interesting" faces (cycles) remain. regards, chip
From: Chip Eastham on 25 May 2010 09:57 On May 25, 9:49 am, Chip Eastham <hardm...(a)gmail.com> wrote: > On May 25, 8:01 am, Rolf Wester <rolf.wes...(a)ilt.fraunhofer.de> wrote: > > > Hi, > > > I would like to determine the edges belonging to the faces of a planar graph given the vertexes and their corresponding neighbors. > > For the case that all faces are triangles I have found a simple algorithm but I have no idea how to do it in case of 4 or more edges. > > Is there any algorithm for this problem? > > > Many thanks in advance > > > Rolf > > Hi, Rolf: > > You may be interested in the Boost Graph Library > approach: > > [Planar Face Traversal -- Boost Graph Library]http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/planar_face_trave... > > If the planar graph is biconnected, and we > include the "unbounded" face, then each edge > belongs to exactly two faces, each vertex > belongs to as many faces as its degree, and > given the number of edges and vertices, the > number of faces can be computed from Euler's > formula. If not biconnected, you may want to > (repeatedly) trim away vertices of degree one > until only "interesting" faces (cycles) remain. > > regards, chip A recent bit of discussion of the algorithm behind the Boost code and references here: [Reporting all faces in a planar graph -- MathOverflow] http://mathoverflow.net/questions/23811/reporting-all-faces-in-a-planar-graph regards, chip
From: Rolf Wester on 25 May 2010 11:19
Hi, Chip thank you very much for your help. Now I know how I can do it. Regards Rolf On 05/25/2010 03:49 PM, Chip Eastham wrote: > On May 25, 8:01 am, Rolf Wester<rolf.wes...(a)ilt.fraunhofer.de> wrote: >> Hi, >> >> I would like to determine the edges belonging to the faces of a planar graph given the vertexes and their corresponding neighbors. >> For the case that all faces are triangles I have found a simple algorithm but I have no idea how to do it in case of 4 or more edges. >> Is there any algorithm for this problem? >> >> Many thanks in advance >> >> Rolf > > Hi, Rolf: > > You may be interested in the Boost Graph Library > approach: > > [Planar Face Traversal -- Boost Graph Library] > http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/planar_face_traversal.html > > If the planar graph is biconnected, and we > include the "unbounded" face, then each edge > belongs to exactly two faces, each vertex > belongs to as many faces as its degree, and > given the number of edges and vertices, the > number of faces can be computed from Euler's > formula. If not biconnected, you may want to > (repeatedly) trim away vertices of degree one > until only "interesting" faces (cycles) remain. > > regards, chip |