I am implementing a graph library and I want to include some basic graph algorithms in it. I have read about planar graphs and I decided to include in my library a function that checks if a graph is planar. I found on the web many efficient algorithms, but they all have the same drawback: they are very hard to implement.
So here is my question: does there exist an algorithm for planarity checking which is easy to understand and to implement?
Best Answer
Several criteria for planarity are listed here: http://en.wikipedia.org/wiki/Planar_graph.
Kuratowski's Theorem gives one possible algorithm, although it is quite slow. http://en.wikipedia.org/wiki/Planar_graph#Kuratowski.27s_and_Wagner.27s_theorems
Hopcraft and Tarjan devised a linear-time algorithm. http://en.wikipedia.org/wiki/Planarity_testing#Path_addition_method
You may find good answers on Stack Overflow.
https://stackoverflow.com/questions/9173490/python-networkx
https://stackoverflow.com/questions/1854711/how-to-check-if-a-graph-is-a-planar-graph-or-not