On Thu, Jul 16, 2009 at 8:45 AM, Maxime van Noppen wrote:

On 07/15/09 16:47, Aaron Windsor wrote:

...

Hi Maxime,

Thank for the answer,

...

If I understand you correctly, you have a graph that's planar and already know the coordinates of vertices in the plane, and you want to create a planar embedding (cyclic ordering of edges around each vertex) that respects your coordinates?

I have a (maximal) planar graph where vertices have coordinates and I want to add new vertices at some precise coordinates and add all possible edges to it to make the graph maximal planar.

I'm new to boost::graph and don't fully understand how the planar embedding is used and therefore what should be in it in order to make make_maximal_planar work.

Given a planar graph G, a planar embedding is an clockwise ordering of the edges adjacent to each vertex as they appear in some drawing of G in the plane. Planar embeddings are not necessarily unique given a particular graph (given a tree, for example, _any_ ordering of edges around vertices creates a valid planar embedding), but a planar embedding serves as a certificate of planarity and is the standard "preprocessing step" in dealing with planar graphs - once you have a planar embedding for a graph, you can pass that planar embedding along with the graph to other functions like make_biconnected_planar, make_maximal_planar, and chrobak_payne_straight_line_drawing. boyer_myrvold_planarity_test can create a planar embedding for you if you give it a planar graph, then you can pass this planar embedding to other functions. A concrete implementation of the planar embedding concept in the BGL would be a vector of vectors of edges: for a vertex with index 5 that has 3 edges adjacent to it, planar_embedding[5][0], planar_embedding[5][1], planar_embedding[5][2] specifies the cyclic order of those edges. In your case, since you already have a plane drawing (given by the coordinates of the vertices in the plane), you don't need boyer_myrvold_planarity_test to tell you that your graph is planar or to create a planar embedding (although it could, it just wouldn't necessarily correspond to the planar embedding implied by your coordinates). But you can still use other functions like make_biconnected_planar and make_maximal_planar - you just need to create the particular planar embedding you have in mind yourself, then pass it to these functions. Functions taking a planar embedding as input will respect the planar embedding that you start from when adding edges/augmenting the embedding. In the specific example you mentioned, if you started with a maximal planar graph + a planar embedding, then added a vertex v somewhere and a few edges adjacent to v, you could still use make_maximal_planar to fill out the rest of the planar embedding as long as you specify at least two edges adjacent to v and add them to the planar embedding first (as this will fix v's relative location in the planar embedding). For example, let's say you have a maximal planar graph G with > 2 vertices and a planar embedding of G, corresponding to a coordinate map that maps all of G's vertices into the the plane. Now you want to add a new vertex v somewhere on the outer face of G - just attach v to 2 other vertices x and y on the outer face of G by adding (v,x) and (v,y) to the graph, insert (v,x) into the planar embedding adjacent to both x and v, and insert (v,y) in the planar embedding adjacent to both y and v. Then call make_maximal_planar, which will add all of the rest of the edges to make the graph maximal planar. Notice that you need to attach x to at least two other vertices, otherwise it's not completely specified whether x lies on the outer face or inside a face. Regards, Aaron