there went my productivity for the day

The Planarity Flash Game, where you have to drag around the vertices of increasingly larger and larger graphs to prove that they are planar. (via Eszter over at Crooked Timber)

It of course got me thinking about the fastest algorithm to planarize a graph that you know is planar. You’d have to define all the quantities you have pre-computed (the smart thing seems to be to find a vertex with minimal degree and work up from there), but it could be an interesting problem. It’s probably been solved already or exists as an exercise in CLR.

One thought on “there went my productivity for the day

  1. You’re the fourth person on my friends list to mention the game. I played a few rounds yesterday. It seemed like something that would be addictive, so I stopped.

Leave a Reply to Linley Cancel 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

This site uses Akismet to reduce spam. Learn how your comment data is processed.