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-15 10:47:51

On Wed, Jul 15, 2009 at 4:56 AM, Maxime van Noppen<maxime_at_[hidden]> wrote:
> Hi,
>
> I can't figure out if it is possible (and if it is, how) to assign
> coordinates to graph vertices on planar graphs. I've tried setting the
> property vertex_index_t to std::pair<int, int> but it doesn't seem to
> work (make_maximal_planar doesn't use them for example).

<snip>

> // The goal is now to make g planar w.r.t. the coordinates
>
> // 1- Either make_connected or add at least one edge to make the graph
> //    connected
>
> // 2- make_biconnected_planar
>
> // 3- make_maximal_planar
> ------------------

<snip>

Hi Maxime,

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? The
boyer_myrvold_planarity_test function can create _a_ planar embedding
if the input graph is planar, but it sounds like you're looking for a
specific planar embedding based off of the coordinates. There's
currently no way to give any of the planar graph functions hints about
the embedding you'd like to create through coordinates, etc., but if
you do create the embedding you want from the coordinates (which you
can do without too much trouble if all of the coordinates are
specified), the rest of the planar graph functions (like make maximal
planar and the chrobak-payne straight line drawing) can be used with
the embedding you provide.

Regards,
Aaron