On Wed, Aug 4, 2010 at 4:12 AM, Anders Wallin
I'm still not really sure what you're asking after reading that post, but let me give it a shot - if you have a graph that looks like: a | b--c--d | e--f--g | h which I think is what you're describing, basically, then you could use planar_face_traversal to create an "outer border" like the red outline in your post.
yes, this is exactly what I want. However I suspect that the planar embedding is not unique (?). As drawn above if we proceed clockwise the output would indeed be a, d, g, h, e, b, a but another planar embedding could for example have the degree-1 adjacent vertices of c in a completely different order and the output would be different.
which means I should probably create the planar embedding myself, and not delegate to boyer_myrvold_planarity_test as is done in the example. Are there any examples out there of how create a planar embedding? from the example it looks like a std::vector< std::vector<EdgeDescriptor> > would something like this work: [ [(a,c)] ] the row for vertex a. a has only one edge (a,c) [ [ (b,c) ] ] same thing for b [ [ (c,b) , (c,a) , (c,d), (c,f) ] ] the row for vertex c. edges should be traversed in the order (c,b) then (c,a) then (c,d) then (c,f) ... and so on...
Yeah, you're right - there can be many planar embeddings for a graph, and there's no way to specify which one you want boyer_myrvold_planarity_test to generate. So if you already have an implicit ordering in the 2D plane on the edges around each vertex in the graph, you'll want to create the embedding yourself. And yes, you're on the right track in your example to create a planar embedding - using a vector of vectors of edges, each edge should appear twice in the planar embedding, once in the clockwise cyclic order around each vertex the edge is adjacent to. The planar embedding concept documentation (http://www.boost.org/doc/libs/1_43_0/libs/graph/doc/PlanarEmbedding.html) has some more information about what a planar embedding means to the BGL, although I can't find a link to any code that manually constructs a planar embedding. -Aaron