Thread: 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?

Graphs may be the wrong structure to use for the problem you are trying to solve.
Graphs only contain information about edges and connectivity.
The three graphs are the same by definition. A graph is planar if there exists a planar embedding.

Perhaps you are asking whether you can find an embedding where the boundary is given by a specific cycle?
I cannot think of a trivial way to change the boyer-myrvold algorithm for this case because there is no concept of "boundary" in the algorithm. It just tries to find K5 or K3,3.

One way that will work, but may not always be possible is this. Choose your boundary cycle. Find the planar embedding by the algorithm. If you see a path that goes out of the boundary, artificially add a new path that prevents the path from taking that route. Then perform the algorithm again.
e.g. your external cycle is abcda, and the "bad" path goes from a to c, the add a new path bvd (where v is a new vertex).

Note, for graph embeddings, internal and external can always be inverted. There is no way around that in any algorithm. However, you can easily transform it by mapping the embedding on a sphere (then internal and external are symmetric).

Thanks for an excellent response.

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. I've realised you can find the cycles (smallest set of smallest rings/minimum cycle basis) in linear time if you do an embedding. This is great, but occasionally fails because of the above problem. If however I could ensure the graphs are truly planar (in my sense of the word) then it would work. Needless to say if the idea is to find the cycles then I don't know if it is a cycle yet.

I will keep looking at this. 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. This would probably work, if I could find a way to do it. Thanks again.

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.

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.

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.

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.

Thanks, you raise some really interesting points. I should try and clarify that the whole point is that the mathematical way of looking at a graph is not the same as a chemical way of looking at a graph, so applying graph theory to chemical graphs is not straightforward. I realise this is a maths forum and not a chemistry one, so i will try to restrict myself to the maths.

Yes you are right when you talk about connectivity, I guess when I say stretch I mean that a chemical graph as drawn on paper is kind of fixed, in that a bond which crosses over another cannot be considered planar, yet graph theory ignores this. I'm saying is there a way to make a planarity-test algorithm take this into consideration.

Twistane is actually a great example of what I mean. The Boyer-Myrvold test will embed it as you say - a hexagon. But chemically it should be seen as the 10-sided non-planar version, and should fail the planarity test. So from a chemical perspective it is non-planar, but mathematically it is planar. If the planarity test was forced to choose the larger external face it would realise that it is non-planar from a chemical perspective. However, I suspect there are structures out there where this may not be the case.

As for the SSSR algorithm, the point is that I am not aware of any algorithm which finds the SSSR in anything less than O(n^3). So if the point is to find the SSSR in linear time I want to embed first because then most algorithms can be done in linear time. If I do the planarity test, embedding and a planar face traversal it is in O(n) time. I did this with the boost graph library. It works for a lot of graphs but then does weird things to fused rings like inverting them, so the rings it finds are not correct. Anyway, I'm beginning to think this is not easy to fix and am abandoning this for another linear time method I've stumbled on which I think does work.

Originally Posted by mrchem

the mathematical way of looking at a graph is not the same as a chemical way of looking at a graph

I totally agree. Unfortunately the chemical way of deciding how to draw a particular compound in the 'right' way is to ask a chemist In other words, it is often a matter of visual perception and convention rather than some algorithm.

a bond which crosses over another cannot be considered planar, yet graph theory ignores this. I'm saying is there a way to make a planarity-test algorithm take this into consideration.

Given a set of coordinates for a structure - that is, a laid-out diagram - it is easy to test if bonds cross using a line intersection method. Most 2D geometry libraries would have this. Of course, this requires the structure to be laid out first...

But chemically it should be seen as the 10-sided non-planar version, and should fail the planarity test. So from a chemical perspective it is non-planar, but mathematically it is planar.

Although I know what you mean by "...chemically it should be..", I'm trying to work out why that is true. Perhaps the answer is that twistane is a 3D structure, not flat. Consider fullerenes; I have been trying to implement a Schlegel layout algorithm from a paper (which required a planar embedding, which is what lead me to this thread which 'squash' the sphere into a net. Although useful, a more chemical representation would be a projection of the 3D points of the fullerene onto a plane.

A mathematically interesting question here might be : since all molecules are necessarily 3D (not 4D or 5D) graphs, does this make it easier for cycle-finding algorithms when run on chemicals?

Anyway, I'm beginning to think this is not easy to fix and am abandoning this for another linear time method I've stumbled on which I think does work.

I don't mean to put you off experimenting to find faster methods. It is definitely worthwhile to ask if there are better ways to get the SSSR as they are used quite a bit (I understand). So best of luck.

Finally, here is a link - if it is of interest - to my blog, which has some recent posts on cycles (circuits?) in graphs and molecules.