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

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-08-31 07:42:41

On 8/30/07, Jens Müller <jens.mueller_at_[hidden]> wrote:
> I am porting LEDA code to BGL, including code dealing with planar graphs.
>
> I have code like this:
>
> e2 = G.face_cycle_succ(e1);
>
> LEDA documentation says "For an edge e of a map G let face_cycle_succ(e)
> = cyclic_adj_pred(reversal(e))"
>
> I suppose there currently isn't any direct support for such an operation?
>
> As far as I understand, I would have to get the embedding[target(e,g)]
> and then look for e there, and take the predecessor of e, right?
>
> I suppose in an undirected graph edges and their "reversal" (i.e., the
> edge descriptor you get when you get the edge from the other end) are equal?
>
> I think directly supporting this would be a nice addition.
>
> Furthermore, I think LEDA can do this in O(1), which we cannot. Well,
> amortized it should be something like O(1), no? The only solution to
> this problem would probably be storing the embedding in the graph object.
>

Yes, you're right - there's no direct support for this kind of
operation in constant time. That's not to say that you couldn't create
such a mapping, depending on how you're storing the planar embedding,
but the basic concept doesn't support efficient access of predecessors
and successors within the embedding. And yes, you can still do it in
amortized O(1) time - in fact, the planar_face_traversal algorithm
builds such a map between edges and their successors for its
traversal.

The idea was that if you want to do the sort of traversal you're
describing, the planar face traversal is the right place to do it.
With appropriately defined visitors, you can, for example, triangulate
a planar graph or create the dual of a planar graph. Are you at
liberty to say what you're doing with your traversal? Maybe you could
do it with a visitor and the planar face traversal instead.

>
> Another issue I have is adding an edge to a planar graph while
> preserving the embedding.
>
> E.g., in LEDA, I have code like this:
>
> newEdges.append(x = G.new_edge(e3,v));
> newEdges.append(e1 = G.new_edge(e1,w));
> G.set_reversal(x, e1);
>
>  From the LEDA docs:
>
> "edge   G.new_edge(edge e, node w, int dir=leda::behind)
>                 adds a new edge x = (source(e), w) to G. x is inserted in front
> of (dir=leda::before) or behind (dir=leda::behind) edge e into adj$
> \_$edges(source(e)) and appended to in$ \_$edges(w) (if G is directed)
> or adj$ \_$edges(w) (if G is undirected). Here leda::before and
> leda::behind are predefined constants. The operation returns the new edge x.
> Precondition source(e)! = w if G is undirected."
>
> It seems to me that there is only one adjacent edges list for a vertex,
> that represents the planar embedding if it has been correctly computed
> and not invalidated.
>
> Well, what I want to say: Functions that can add edges to an embedding
> would be really cool. Of course, it would be the user's obligation not
> to invalidate the embedding.

I do see your point and agree with you that this would be nice to
have, but again, take another look at planar_face_traversal (the
make_maximal_planar code is a good example of how to use it), since I
did mean for it to be a convenient way of adding edges to a planar
graph. I'll think about this a little bit more - there may be another
clean way to support accessing/adding edges to a planar graph. It's
not that it's impossible to do, but I think it depends a little too
much on how the embedding is stored. If you use a vector to store the
edges in your embedding, for example, you're not going to be get this
feature in constant time. The main obstacle is that, as you've
mentioned, since we're dealing with undirected graphs, each edge {u,v}
is going to appear twice: once on u's embedding and once on v's
embedding.

And this is also sort of a dangerous thing to support - it would be
better to have an implementation of a dynamic planarity testing
algorithm for this, since it's really not clear when you add an
arbitrary edges whether or not the graph is still planar, and the
complexity of testing whether or not a planar embedding is the same as
actually computing it in the first place.

Regards,
Aaron