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... thanks, Anders