Game Development Stack Exchange is a question and answer site for professional and independent game developers. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
up vote 2 down vote accepted

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:, particulary the planar graph drawing algorithm.

share|improve this answer
Thanks. That's what I looked for. Now I just have to implement that^^ – M0rgenstern Jun 11 '12 at 19:14

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.