## 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.*

well there goes my work day!

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

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

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

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

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

But, seriously, there must be a good

algorithmfor this, right? Could you design a computer program that could effectively play this?First attempt time:

222.821

Keep trying.

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.

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