When is a graph planar?

A graph G is planar if and only if xxx.

What can xxx be substituted for? Note that this is from a topological POV so a graph is a 1-dim cw complex and I guess the fundamental group should be used somehow.

• en.wikipedia.org/wiki/… – Qiaochu Yuan Nov 12 '10 at 12:04
• The fundamental group is not very useful in this context, as each finite graph is homotopy equivalent to a bouquet of circles. – Robin Chapman Nov 12 '10 at 14:08

Kuratowski: A graph $G$ is planar iff $G$ does not contain a sub division of $K_{5}$ or $K_{3,3}$.
There are lots of characterizations of planar graphs, e.g. Kuratowski's theorem as already mentioned. Another is Whitney's theorem that a finite graph $G$ is planar if and only if the dual matroid to the matroid of $G$ is graphic (also comes from a graph).