Planarity is indeed an addictive flash game. I just did level 13 in 19:30 minutes. What are your scores like?

This game was also featured in that cool Multi-Touch touchscreen video you might have seen some month ago.

There is however a rather generic approach that will lead you to a solution rather reliably. Don't just move around random vertices, instead pick one and move it into the center, now grow the solution from that center node. The higher the level, the less space you'll have, so keep it dense! Always look at all "new neighbours" first, where to place them best to avoid having to swap them later.

But by just walking around clockwise around the "convex hull" of what you've built so far, you get a pretty good network. I guess you can even prove it that you'll be able to solve it in O(n) that way when done right.

In level 13 I this worked quite good for me, except I ran out of space some time. I then picked a random outer node, moved it to the very upper left, and moved the "covex hull" to the borders of the screen.

From time to time you'll see you've made a mistake, but this can usually be solved by mirroring some group in your network.

Update: Level 14 in 18:13 Minutes. Looked like this:

with a small problem at the top edge of screen due to lack of space there.

Update: Level 15 in 14:01 Minutes. The schema works perfectly, you have to touch each node at most twice (once when discovering, and maybe switch place with a sibling when discovering the new neighbours). All changes are local, and you don't actually look at the lines, just at the colored nodes.

Unless of course you run out of space and have to rearrange.