Aaron Windsor wrote:
When I'm saying "BidirectionalGraph", I'm talking about the concept (http://www.boost.org/libs/graph/doc/BidirectionalGraph.html), which can be modeled by both undirected and directed graphs. When you're saying "bidirectional graph", it seems to me that you're talking about a directed graph that models the BidirectionalGraph concept (an adjacency_list with the bidirectionalS property selector is such a graph). But undirected graphs can also model the BidirectionalGraph concept (for example, an adjacency_list with the undirectedS property selector).
The planarity test/embedding algorithms require an undirected graph that models the concepts VertexAndEdgeListGraph and IncidenceGraph (both described here: http://www.boost.org/libs/graph/doc/graph_concepts.html). Furthermore, BidirectionalGraph is a refinement of IncidenceGraph, so if you have an undirected graph that models BidirectionalGraph and VertexAndEdgeListGraph, that will work as well. But it must be an undirected graph.
Hmm, ok, I think I got it. Would it be possible to treat directed graphs as well? After all, a directed graph is conceptually the same as an undirected graph with additional edge labels designating source and target ... Jens