Hi, I was looking to traverse a planar graph and report all the faces in the graph (vertices in either clockwise or counterclockwise order). I have build a random planar graph generator that creates a connected graph with iterative edge addition and needed a solution to report all the faces that were created in the final graph. I was contemplating several strategies such as doing a sweep line algorithm and tracking the areas between lines or tracking the faces as I generate the graph however I have not been able to find much material regarding this matter and was wondering where I could find some assistance/ideas how to do this.
So far I found a Boost algorithm here http://www.boost.org/doc/libs/1_36_0/boost/graph/planar_face_traversal.hpp however I am having a lot of trouble decrypting the boost library to determine how it is done.
Any thoughts, ideas or existing algorithms would be welcome.
Best Answer
I'll assume the graph is connected, and that you have the clockwise or counterclockwise ordering of the edges around each vertex. Then it's easy, given a directed edge e, to walk around the face whose counterclockwise boundary contains e. So make a list of all directed edges (i. e., two copies of each undirected edge). Pick one directed edge, walk counterclockwise around its face, and cross off all the directed edges you traverse. That's one face. Pick a directed edge you haven't crossed off yet and walk around its face the same way. Keep doing that until you've crossed off all of the edges. (Note that the "counterclockwise" boundary of the exterior unbounded face actually goes clockwise around the outside of the graph.)
If the graph isn't assumed to be connected, then things could be more complicated, since the boundary of a face could have multiple connected components. In that case, you might as well use a standard general-purpose algorithm for computing planar subdivisions. I don't think you lose anything (in asymptotic complexity, anyway) by doing this.
I don't have it in front of me, so I can't tell you with certainty, but I think this is covered in "The Dutch Book" (Computational Geometry: Algorithms and Applications, by de Berg et al.). In any case, that's one of the main references for these types of computations.