Re: [boost] Topological Embedding of Graphs?

From: Jens Müller (jens.mueller_at_[hidden])
Date: 2007-07-21 05:10:18

Ethan Kim wrote:
> Hi,
> 
> I'm a new user to the Boost library in general, and I was wondering if
> the following feature is built into the BGL. When dealing with graphs
> with an embedding, one can encode the embedding by giving a cyclic
> ordering of adjacent vertices, for each vertex.
> 
> I've looked at the adjacency_list's documentation, and after a few
> tests, I discovered that such cyclic ordering is not guaranteed. How
> can one go about doing this? I can set up the input so that the edge
> list is given in that order.
> 
> Any help would be much appreciated. Thanks!

There is an implementation of planar embeddings by Aaron Windsor. The 
embedding is not (yet?) integrated in the adjacency_list, but created as 
a map from vertices to lists of edges. He has implemented the 
Boyer-Myrvold algorithm to create such an embedding.

You will find it if you search in this mailing list for "planar" in the 
subject ...

It's cool that there is another prospective user!

Cheers,

Jens