Re: [boost] [BGL] Tools for planar graph testing/embedding/drawing in the vault

From: Aaron Windsor (aaron.windsor_at_[hidden])
Date: 2007-04-01 15:36:00

On 4/1/07, Jens Müller <jens.mueller_at_[hidden]> wrote:
> Aaron Windsor schrieb:
> > Hi all,
> >
> > I've implemented a small suite of tools for dealing with planar graphs and
> > would like to add it to the BGL. The core of this suite is built around the
> > recent Boyer-Myrvold algorithm for planarity testing/embedding.
> > (see http://www.emis.de/journals/JGAA/accepted/2004/BoyerMyrvold2004.8.3.pdf)
>
> Wow - just in time. I am re-implementing a planar separator algorithm
> which was done using LEDA graphs. I'll take a look at it, but not today ...

Hi Jens,

A planar separator algorithm would be a very nice addition!

>
> Have you specified concepts for planar graphs?
>
> If so, maybe I can pimp the leda_graph.hpp accordingly.

Yes - basically, the concept for a "planar graph" is a graph plus a planar
embedding. A planar embedding is a property map that maps any vertex
in the graph to an ordered list of edges adjacent to that vertex. The ordered
list of edges corresponds to the clockwise ordering of those edges in a
plane drawing of the graph. So, it's a little more flexible than having, say,
a PlanarGraph concept that refines one of the other graph concepts in the
BGL - if you actually want the algorithm to re-arrange the edges in your
graph, it can do so, through the indirection of a property map. But you
can also store the planar embedding externally, with a vector of vectors,
for example.

Right now, the concept of a planar embedding is an lvalue property map
p that supports p[v].begin(), p[v].end(), p[v].push_back(Edge), p[v].clear(),
but I'm still open to changing this - maybe having free functions begin, end
push_back, and clear that take a planar embedding's value_type as the
template parameter and an argument to the function would be a little more
general, since they could default to actually calling begin(), end(),
push_back(Edge), and clear() member functions, but would be a little easier
to override in the case you don't want to store the planar embedding in
something that acts like an STL container.

Regards,
Aaron