Boost logo

Boost :

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

Boost list run by bdawes at, gregod at, cpdaniel at, john at