Algorithm for planarity test in graphs

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

I think @K. Hu's suggestion of an algorithm based on Kuratowski's theorem must be the easiest to understand and implement. Let's try to write it in pseudocode:

is_planar(G):
  If G is the empty graph, return TRUE.
  If G is isomorphic to K_(3,3) or K_5, return FALSE.
  For each vertex V of G:
    Let H be a copy of G with V and all adjacent edges removed.
    If not is_planar(H), return FALSE.
  For each edge E of G:
    Let H be a copy of G with E removed.
    If not is_planar(H), return FALSE.
  For each edge E of G:
    Let H be a copy of G with E contracted.
    If not is_planar(H), return FALSE.
  return TRUE.

This will typically only terminate in a reasonable amount of time for very small graphs. However, there are optimizations such as memoization that can improve the running time somewhat without altering the overall structure of the program. Possibly it could be extended to work for larger graphs of an unpathological nature, or at least those with certain nice properties.

Additionally, it has the benefit of generalizing easily to other topological surfaces as long as the forbidden minors are known.