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.

This entry was posted in Uncategorized and tagged . Bookmark the permalink.

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

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

You are commenting using your 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.