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@cs.kent.edu