Home > Challenge, Geometry > Great Graph Game

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.

Click here to see more in Challenge.


  1. Rachele
    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. 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?

  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. Leandra Stewart
    April 4, 2011 at 8:12 pm

    First attempt time:

  8. April 4, 2011 at 8:27 pm

    Keep trying.

  9. 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.

  10. April 7, 2011 at 10:01 pm

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

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: