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?