“Untangle”-Game AI

Question

I am trying to program an AI for such untangle games like Untangle game.

I tried the following possibilities:

1) Just set one node after the other to a random place. If every node was moved once, start over with the first node in the list.

2) First move all nodes which have the most wrong connections. If all were moved once, move the nodes which have the fewest (but not 0) wrong connections. If all were moved but there are some left, move all which are left. If none are left start over.

3) Just 2) bust starting with the nodes with the fewest connections.

4)/5) As 2) and 3) but when I didn't move nodes which have only correct connections.

All of these approaches are too slow and inefficient.

Can anyone suggest a solution which does not depend so much on fortune?

Answer 1

I believe what you are looking for is a planar graph embedding algorithm.

If you want to solve the problem "properly" (in linear time), this thesis linked in this math.SE question seems to be what you are looking for.

Here is another paper on the subject A Linear Time Algorithm for Embedding Graphs in an Arbitrary Surface. Be aware that they are quite math heavy.

Edit: I found this implementation which should help: http://code.google.com/p/planarity/, particulary the planar graph drawing algorithm.