UNDIRECTED EDGE GEOGRAPHY

The game of edge geography is played by two players who alternately mo ve a token on a graph from one vertex to an adjacent vertex, erasing t he edge in between. The player who first has no legal move is the lose r. We show that the decision problem of determining whether a position in this game is a win for the first player is PSPACE-complete. Furthe r, the problem remains PSPACE-complete when restricted to planar graph s with maximum degree 3. However, if the underlying graph is bipartite we provide (1) a linear algebraic characterization of the P- and N-po sitions, yielding (2) a polynomial time algorithm for deciding whether any given position is P or N, and also (3) a polynomial time algorith m to find winning moves.