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?