Home > Challenge, Geometry > Great Graph Game

## Great Graph Game

Wow, is this fun:  a graph theory-based game called Planarity.

http://www.planarity.net/

Given a set of vertices and edges, your job is to untangle the graph so that no two edges intersect.  In essence, you are proving that the given graph is indeed a planar graph.

If it takes you a long time to succeed, just tell your friends you got caught up thinking about questions like “How can I prove it’s always possible to untangle this graph?” and “I wonder how many more edges I could add while keeping this puzzle solvable?”  That’s what I tell people.

www.MrHonner.com

1. April 1, 2011 at 10:20 am

well there goes my work day!

2. April 1, 2011 at 12:27 pm

If your boss gives you a hard time, just say “I’m teaching myself Graph Theory.”

3. April 1, 2011 at 11:55 pm

I beat one of them in 26.4 seconds and it still said it wasn’t fast enough! Does it ever compliment you?

4. April 2, 2011 at 9:10 am

I don’t think so. Like any good teacher, it always tell you that you can do better.

5. April 3, 2011 at 7:26 pm

54.864 seconds. I aimed for under a minute so I had about five seconds to spare. Good enough for me.

6. April 3, 2011 at 9:27 pm

I just did it in 23 seconds. I must be a natural.

But, seriously, there must be a good algorithm for this, right? Could you design a computer program that could effectively play this?

7. April 4, 2011 at 8:12 pm

First attempt time:
222.821

8. April 4, 2011 at 8:27 pm

Keep trying.

9. April 7, 2011 at 3:54 pm

Planarity can be tested in linear time (http://en.wikipedia.org/wiki/Planarity_testing), but creating a planar embedding of a graph is (I believe) NP complete.

10. April 7, 2011 at 10:01 pm

Can you provide a clear explanation of this fact? Because Wikipedia can’t.