[boblol123]

Take the vertex whose vertices cross the biggest number of other vertices and move it. Repeat until nothing crosses. I remember this problem in maths ages ago, there is a way to know if you can't untangle something- look up the water gas electricity problem

[gjm11]

A graph is nonplanar if and only if it has a subgraph that looks like either (1) five vertices all connected to one another or (2) two sets of three vertices, with every vertex in one set connected to every vertex in the other.

"Looks like" means: can be turned into by repeatedly replacing -o- (a vertex with two edges coming out of it) with -- (a single edge between the vertex's two old neighbours).

See http://en.wikipedia.org/wiki/Planar_graph for details.