Graph theory boyer-myrvold planarity test thinks non-planar graph is planar

I am trying to find a way to identify if a graph is planar or not. Using the boost graph library there is the boyer-myrvold algorithm. This seems to work except it finds some non-planar graphs are planar. This is because edges are stretched out of position.

For example see the three graphs at the top of this page. I want the algorithm to recognise that the first graph is non-planar and not distort it to the other planar graphs. This may have to be done either by using another algorithm, or modifying the boyer-myrvold algorithm so that restrictions are imposed on stretching edges, or on inverting (flipping) faces so edges which should be external do not become internal.

Anybody able to help?

A drawing of a (chemical) graph is not the same as the graph itself

Hi, I'm a biochemist working with graph-theroy algorithms, and I've been looking at the area of SSSRs and planar embeddings this week.

Quote:

Originally Posted by

**mrchem** To explain I am starting with a graph. this is a graph of a chemical structure. The bonds have fixed distance and should not be stretched.

The images at the top of that boost page are misleading; the Boyer-Myrvold algorithm does not work with 2D coordinates, so no bonds are stretched in the process. I haven't yet read the paper closely enough, but I suspect that only the connectivity is used to determine planarity of a graph.

Quote:

I've realised you can find the cycles (smallest set of smallest rings/minimum cycle basis) in linear time if you do an embedding.

Well possibly, but I understood that finding the SSSR/MCB is a possible first step to making an embedding, so this seems like the wrong way round. On the other hand, I am only just learning about cycle bases and such like, so I may be wrong.

Quote:

I am now wondering if it is possible to find the embedding of a graph with the maximal external face. That is to try different embeddings, and choose the one that has the largest number of edges exposed to the external face.

Twistane is one of my current favourite examples of a fused ring structure. It has a planar embedding (a drawing with no line crossings) where the boundary is a hexagon. It also has a nicer, more chemical-looking, drawing with a 10-atom ring boundary but with two crossings. So I'm not sure that picking the embedding with the largest boundary will work, if I've understood your suggestion right.