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

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-08-31 08:57:02

Aaron Windsor wrote:
> 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.

I am doing "triangulating breadth first search". It is described in 
http://i11www.iti.uni-karlsruhe.de/teaching/theses/files/studienarbeit-rahmani-06.pdf 
(p. 45, unfortunately only in German).

I think I can send you the relevant code in private mail.

> 
>>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.

Well, then boost::embedding_traits<Embedding>::edges_insertable would 
have to be boost::edges_not_insertable ;-)

> 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.

What exactly is the obstacle there?

> 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.
> 

Hmm, ok ... Here, it of course concerns adding an edge inside a face of 
the current embedding. It's a special variant of triangulation, as you 
seem  to have correctly guessed.

Bye,

Jens