Re: [Boost-users] [Graph] Defining coordinates for vertices

Subject: Re: [Boost-users] [Graph] Defining coordinates for vertices
From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2009-07-16 21:35:18

On Thu, Jul 16, 2009 at 8:45 AM, Maxime van Noppen<maxime_at_[hidden]> 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