Search code examples
algorithmgraphgraph-theoryplanar-graph

Planarity testing algorithm implementation

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?

Solution

  • 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.