Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
2  
You could just use Sage which has a very efficient planarity algorithm built in. You won't need to understand it to use it. It also will probably have any other functions you want, or if it doesn't, you could help make Sage better for everyone by implementing just those one or two algorithms you need that are not already built-in. No need to reinvent the wheel. sagemath.org –  Graphth Aug 8 '12 at 17:50
1  
Actually it is not that hard to implement the planarity-checking algorithm; in my college people did it in their second programming course (the first one where they learnt C). It just takes some time and patience. –  ShreevatsaR Nov 1 '12 at 17:51
1  
What language are you implementing your library in, BTW? –  ShreevatsaR Nov 2 '12 at 5:47
    
@ShreevatsaR in c++ –  Rondogiannis Aristophanes Nov 2 '12 at 18:02

2 Answers 2

up vote 10 down vote accepted
+100

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.

http://stackoverflow.com/questions/9173490/python-networkx

http://stackoverflow.com/questions/1854711/how-to-check-if-a-graph-is-a-planar-graph-or-not

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.