As I mentioned briefly here, next year's graph drawing contest will include a prize for the best computer game based on graph drawing. As inspiration, I thought I'd briefly describe what I think are the best games (computer or otherwise) that I know about already that are based on graph drawing.

Planarity is a puzzle in which you are presented with a random-looking circular layout of a graph, with many edge crossings, and must move the vertices to turn it into a planar drawing. Once you complete one graph, you move on to the next level with a bigger graph. The online version that I know about bases its scores on how quickly you can untangle the graph, but the same game has also led to a mini-industry of research papers asking how many vertices you can guarantee to leave in place while moving the rest to eliminate all the crossings, or how many crossings can be formed in an obfuscated drawing of a planar graph [KSV07, RV08, SW08, V08, BDHLMW08, GKOSSW09, C10, KPRSV11].

Bridges is another computer puzzle, in which you are presented with a set of vertices in a grid, each with a degree already given to it, and you must find a connected graph drawing in which all edges are axis-parallel and each vertex has the specified degree. To make it a little more complicated, the game allows multigraphs in which two parallel edges may connect the same two vertices, so the degrees may range from 1 to 8.

Masyu is a belated addition to this list, that I haven't actually played. You are given a collection of black points (vertices) and white points (non-bends) on a grid; the task is to find a planar grid drawing of a cycle through the black vertices, in which the paths between black vertices form polygonal chains of axis-parallel line segments, the segments incident to each black vertex are perpendicular, and paths can only bend at the unmarked points.

Metroville is a game in which one is given a fixed set of vertices, and a set of confluent junctions that are fixed in position but can rotate freely; the task is to rotate the junctions so that the confluent graph drawing that they form contains a specified path. I've only seen this as a physical game but it could easily be computerized.

Sprouts is a two-player pencil-and-paper game invented by John Conway and Mike Paterson, and popularized in the late 1960s by Martin Gardner, in which the two players cooperate to form a graph drawing. Initially, there are a given number of vertices placed, with no edges; then, each move connects two existing vertices (up to a maximum vertex degree of three) by a path through a new vertex that may not cross any of the existing edges. Depending on the choice of rules, the last player who can move either wins or loses.

The three utilities puzzle is more of a brain teaser than something that could be turned into a computer game, but is also about graph drawing and planarity.

Additionally, there are any number of games and puzzles that are played on a grid of some sort and in which the object of the game involves graph connectivity in some way; notable examples include Go, Hex, Bridg-It, Dots and Boxes (in the dual formulation in which one is given a graph and must delete edges to create isolated vertices), Twixt, TransAmerica, and Saboteur. There are also maker-breaker games in which players add edges to a graph to create or avoid creating certain subgraphs (for instance, tic-tac-toe can be expressed in this way as trying to create a star or a matching in a bipartite graph) and pursuit-evasion games on graphs. But unlike the ones I've described in more detail above, I don't really think of any of these as graph drawing games, because they don't really address any of the core principles of graph drawing.