Great Graph Game

Published by patrick honner on

graph gameWow, 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.

patrick honner

Math teacher in Brooklyn, New York


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:

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 (, 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.

Leave a Reply

Your email address will not be published. Required fields are marked *


Get every new post delivered to your Inbox

Join other followers: