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.