Great Graph Game
Wow, is this fun: a graph theory-based game called Planarity.
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.
10 Comments
Rachele · April 1, 2011 at 10:20 am
well there goes my work day!
MrHonner · April 1, 2011 at 12:27 pm
If your boss gives you a hard time, just say “I’m teaching myself Graph Theory.”
Ahmed Gouda · 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?
MrHonner · 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.
Alan · 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.
MrHonner · 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?
Leandra Stewart · April 4, 2011 at 8:12 pm
First attempt time:
222.821
MrHonner · April 4, 2011 at 8:27 pm
Keep trying.
Tao · 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.
MrHonner · April 7, 2011 at 10:01 pm
Can you provide a clear explanation of this fact? Because Wikipedia can’t.