A modular approach to Sprouts ?
Sprouts is a two players game that was first introduced by M.S. Patterson and J.H. Conway in 1967. There are two players A and B that, starting from a set of x0 vertices, build a graph by alternatively connecting any two vertices with degree less than three with an edge, and by drawing a new vertex on this new edge. A move is allowed only if the new connection maintains the planarity of the graph. The player that executes the last possible move is the winner. We study some new topological properties of this game and we show their effectiveness by giving a complete analysis of the case x0=7 for which, to the best of our knowledge, no formal proof has been previously given.
games planar graphs algorithms