If you have seen my last question: trapped inside a Graph : Find paths along edges that do not cross any edges

How do you split an entire graph into distinct shapes 'trapped' inside the graph(like the ones described in my last question) with good complexity?

Please note each vertex has a fixed x,y position.

Graph split into shapes

What I am doing now is iterating over all edges and then starting to traverse while always taking the rightmost turn. This does split the graph into distinct shapes. Then I eliminate all the excess shapes (that are repeats of previous shapes) and return the result.

The complexity of this algorithm is O(E2). I am wondering if I could do it in O(E) by removing edges I already traversed previously. My current implementation of that returns unexpected results.

  • \$\begingroup\$ have you tried cs.stackexchange.com , they should know they're graph theory and algorithms better. \$\endgroup\$ Nov 13 '12 at 19:10
  • \$\begingroup\$ One question about this problem: are you looking for a splitting of an abstract graph - i.e., just a set of nodes and edges - or a concrete embedding of the graph in the plane (where the nodes have XY coordinates, for instance)? If it's the former, then it's worth pointing out that such a splitting is far from unique and you'd want to define additional criteria on it. \$\endgroup\$ Nov 13 '12 at 21:17
  • \$\begingroup\$ For example, in your figure the tendril that extends into the orange area from the vertex shared by the blue and green triangles could as easily be placed external to the graph: just 'flip' the blue and green triangles over, placing their other shared vertex on the inside boundary and the vertex with the tendril on the outer edge. If you don't have an embedding - if you don't have those XY coordinates for your graph - then 'faces' of the graph are almost arbitrary, and if you do have an embedding then you're talking more about polygons than a general graph... \$\endgroup\$ Nov 13 '12 at 21:18
  • \$\begingroup\$ @StevenStadnicki It see what you mean. It is the (2) option. If you can edit the question to clarify each vertex is in a specific x,y point, that would be great. \$\endgroup\$
    – AturSams
    Nov 14 '12 at 22:22

The following simple algorithm should give you O(E) solution:

  1. Create a directed graph from your graph by adding arcs to both directions for each edge in your initial graph
  2. Start traversing the graph from any node with the current logic of always turning to the same direction in junctions
  3. Only proceed through arcs that are directed away from the node
  4. Remove the arc after traversing it
  5. Remove the node if it has zero connections left
  6. When you reach the starting node, you have found a polygon
  7. Repeat from 2. until no nodes are left
  • \$\begingroup\$ Yup, this is pretty much what I went with. I had a bug in the implementation so I tried to work around it with a different approach to this and it works fine in O(E) without counting the number of times the shapes use each edge. \$\endgroup\$
    – AturSams
    Nov 14 '12 at 22:19

After some trial and error I found a solution.

  1. Iterate over all edges, one by one.
  2. Starts a path from each edge in it's turn, saving the shape as you go, taking the rightmost turn in each vertex.
  3. After traversing three edges, check if any previous shape uses these three edges*.
  4. If not continue to traverse until you reach the starting point and save the loop.

    • To check if a previous path used three edges, create a list of arrays of paths. The list is indexed from 0 .. (E - 1) where E is the # of edges. The array at index i in the list contains all the paths that use edge i.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.