Finding polygons within an undirected Graph

Question

Please see Image: https://i.sstatic.net/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!

Answer 1

For starters lets get rid of the degenerate edges (JK and JL in your example): Find the vertices with a single edge and remove them from the graph. Note that this removal could also create another degenerate edge, so every time you remove a vertex A and the edge AB, take another look at vertex B to see if it is now also degenerate.

Now notice that while each vertex can be involved in any number of polygons, each edge is involved in exactly two. I'd thus suggest that we can make life simpler for ourselves by walking over the edges rather than the vertices.

1. Associate two boolean fields with each edge to record if the left and right polygons have been found. These fields should initially all be false.
2. Choose an arbitrary edge, let's call it AB
   1. if AB.right is false:
      1. Create an empty list L in which to store the polygon edges
      2. Set AB.right to true and add AB to L
      3. Iterate the edges of vertex B to find the next edge of the polygon. Imagine you're driving from A to B, the next edge is the one that forces you to make the sharpest-possible right-hand turn at B. I feel sure that the dot-product of the edge vectors will make this search trivial, but it's been too long for me to recall the details.
      4. Recurse steps 2 and 3 for this next edge (setting the right variable to true and adding the edges to L) until you hit an edge where right is already true. This will be the edge that you started on - You've found a complete polygon and you've eliminated a bunch of edges from your search space!
   2. if AB.left is false, do the same procedure as above, only this time you're driving in the opposite direction (from B towards A) and you're setting the left fields to true as you go. Note that you're still trying to make the sharpest-possible right-hand turn at each vertex. This will produce another polygon and eliminate another bunch of edges from your search.
3. Repeat until the left and right fields of every edge are true.

We'll have produced a list of polygons, but this list will contain some polygons that we don't want - the ones that contain the exterior spaces of your plane (in your example image, these would be XZY and ACDHJIB). These can be detected by checking the winding order of the vertices. We were making right-hand turns at every vertex, so the polygons we want will show a clockwise winding order.

Answer 2

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.