Algorithm for planarity test in graphs

Question

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?

Answer 1

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

Answer 2

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.

Answer 3

The Left right planarity test isn't very hard to understand. The idea is to use a deep first search spanning tree $T$ of the graph as a skeleton and try to find a subset $L$ of the edges of the cograph $C$ of $T$ such that $R=C-L$ and $L$ can be placed on the right and the left of the tree to obtain a planar graph. If it works the graph is planar else non planar. If the tree is a Hamilton path the situation is rather simple else there is some more things to consider.