Take the 2-minute tour ×

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.


  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!

share|improve this question
I think DFS is a good way to find all the cycles in the graph. Then you want to start with the cycles of length 3 and define those as polygons. Next you need to look at the next size of cycle and check that there isn't a set of it's vertices that make up an entire defined polygon already - if there isn't then this cycle is a new polygon. Continue until you run out of cycles. –  Helen Mar 21 '12 at 16:50
Thanks for your answer Helen. This might give us some results. But there are some failure cases here. Consider that the polygon XYZ is moved such that it is completely contained within EFGH. Your strategy would yield first XYZ and then EFGH as acceptable polygons disregarding the obvious overlap. I guess we could solve this problem by testing each vertex for every polygon so that it is not contained in another polygon. That is we are performing area check in addition to Edge chechs. But this is not very elegant and probably expensive. Thoughts? –  Dev.D Mar 21 '12 at 19:46
I was thinking about this last night, and I don't think the problem is well defined enough to be solvable. As there are so many ways that the example graph can be drawn as a planar graph I don't think you can just input a set of vertices and edges and have a solution output. What if I,J were inside the A,B,C,D rectangle and E,G on the outside? In order to check if polygons overlap you need to know how they are drawn in relation to each other. You could really do with a coordinate set rather than a set of vertices. –  Helen Mar 22 '12 at 9:28
Hi Helen, for my problem set I can guarantee that the edges will never intersect. If edges do meet , they will always meet at vertices. Thus polygons are either a) completely enclosed by or b) share a common set of edges with or c) are completely disassociated from a given polygon.This is ensured by a prior integrity stage in the pipeline. I'll update the question to reflect this. –  Dev.D Mar 22 '12 at 13:21
Ok in which case use DFS to find all the cycles. Then iterate through all of the cycles to find the ones with no other cyles inside them. Define those as polygons. Iterate through the cycles again to find those with only the defined polygons and no other cycles inside them and define those new cyles (minus the existing polygons inside them) as polygons. Repeat until you run out of cycles. –  Helen Mar 22 '12 at 13:29
show 1 more comment

1 Answer

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.

share|improve this answer
Welcome to SO. I appreciate that the paper you linked to is a paid-for paper, but posting Link Only answers is generally frowned upon here, as link-rot makes the answer meaningless. –  Andrew Oct 22 '12 at 6:38
add comment

Your Answer


