Planarity testing algorithm implementation

Question

I want to write an algorithm that takes as input a graph and returns true if it is planar or false if it is not. I searched around and found tons of algorithms but no easy to understand implementations.

Is there any implementation like Boyer-Myrvold's or anything else available in C++ or Java that does what I ask?

Answer 1

The implementation in Boost of Boyer-Myrvold is pretty understandable and very well-commented.

https://www.boost.org/doc/libs/1_67_0/boost/graph/planar_detail/boyer_myrvold_impl.hpp

I wouldn't try reading the code without reading the original paper first, though.

Answer 2

There is a detailed description of the Path Addition method of Planarity Testing in this thesis (both the mathematical theory and the algorithmic implementation).

The full Java source code is also contained in the appendices supporting:

• Planarity Testing;
• Generating a planar embedding; and
• To cycle through generating all possible planar embeddings of a biconnected graph (in linear time proportional to the number of edges and the number of embeddings to generate all embeddings).