Planarity

A while ago I enjoyed playing Planarity. It is somehow interesting to note, that as with most puzzle games, you'll need to know if the current puzzle has a solution. In case of planarity you want to know, if a randomly chosen graph on $n$ vertices is planar. So what's the math behind it? It's obviously simple enough to be implemented in Flash. I'll see, if the graphs greated are sparse enough to fulfill $#E(G) \leq 3#V(G) − 6$, as that would be my first choice...