Finding polygons within an undirected Graph

问题:

Please see Image: http://i.stack.imgur.com/NPUmR.jpg

I have an undirected graph which contains one or more connected sub graphs. The graph is defined by a set of ordered pairs of connected vertices. There may be upto 300 vertices. The graph is planar.

I need to identify polygons as shown in the Image. Each of the coloured areas in a separate polygon. A rough heuristic could be that polygons are "enclosed regions" between closed edge loops (cycles) in the graph. It's been suggested in similar posts that cycles may be identified using a Depth First traversal and marking visited vertices.

However I'm not sure how to proceed after this to get the desired output as seen in the image.

Requirements :

i) The polygons must not overlap or intersect. i.e : Cycle ABFHDCA is not a valid polygon since this would overlap with Polygon FHGE . Cycle ABFEGHDCA is a valid polygon.

ii) The polygon may have 3 or more edges and polygons must be bounded by edges of the graph. XYZ is a valid polygon although disconnected from the rest of the vertices of the Graph.

iii) Vertices like K and L (i.e. leaves) do not form parts of the polygons. We don't care about edge JK.

Update: iv) In the graph edges do not cross each other. The only place two edges can meet is at a vertex. This is guaranteed to be the case by a preceding stage/algorithm.

Questions:

1. Am I on the right track with the DF travesal to find cycles approach? Would DF traversal give me all the (simple) cycles I need to consider in such cases, esp with XYZ being disconnected from the rest of the graph?

2. Is there an existing alternative algorithm for solving this problem?

Additional notes:

a) I am having trouble in defining this problem in more specific computation geometric terms so am sticking with finding polygons within an undirected graph. I must admit it's been years since I studied graph theory. I'm am brushing it up presently.

b)A solution to this does not seem like a concave/convex hull algorithm. We are talking about a set of connected edges - true polygons, not just a point cloud that needs to be encompassed.

c) The example above is what I could come up with at short notice. I think it covers most of the "edge" cases (pun) :)

Similar Solutions

1. I found a similar post but the accepted solution doesn't seem to generate the correct cycles for this example.

Thanks in advance!

回答1:

An optimal algorithm for extracting the regions of a plane graph: http://www.sciencedirect.com/science/article/pii/016786559390104L

What you want to do is extract polygons/regions from an embedded planar graph. The algorithm is given in the paper above. The time complexity is \Omega (m \log{m}) and space complexity is \Omega (m) where m is the number of edges in the graph.