PSPACE-Complete Two-Color Placement Games
  We show that three placement games, Col, NoGo, and Fjords, are PSPACE-complete on planar graphs. The hardness of Col and Fjords is shown via a reduction from Bounded 2-Player Constraint Logic and NoGo is shown to be hard directly from Col. 
Kyle Burke, Bob Hearn
cs.CC