Re: [boost] [graph] planar: face traversal and connected issues

From: Andrew Sutton (asutton_at_[hidden])
Date: 2007-08-31 09:07:05

> Umm, what I was aiming at is that you would have to store the  
> embedding
> internally in order to achieve something useful. What we need is O(1)
> access to the cyclic (according to the combinatorical embedding)
> successor or predecessor edge of a given edge. It's reversal edge is
> just the same edge, but viewed from the opposite vertex (we need it's
> planar embedding cyclic successor and predecessor there, as well).
>
>
> A planar embedding is an ordering of the incident edges of each  
> vertex.
> Of course, this ordering must be valid in the sense that the graph is
> indeed planar like that.
>
> When I have a square as a graph (four vertices, four edges), I can add
> an additional edge dividing the square in two triangles. Of course,  
> this
> edge would have to be added add the right position in the embedding
> (i.e., the incident edge orderings of the two concerned vertices).

Like I said, I don't know much (anything) about planarity structures  
or algorithms. Maybe I'll spend some time reading up on it.

Andrew Sutton
asutton_at_[hidden]