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.
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.
Originally Posted by mrchem
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.
I've realised you can find the cycles (smallest set of smallest rings/minimum cycle basis) in linear time if you do an embedding.
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.
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.