I investigate complementarity games played on graphs, which model negative externalities embedded in structures of interaction. On the complete graph, the traditional economic analysis applies: the number of agents playing one strategy is proportional to its payoff. I show that, in general and contrary to coordination games, the structure crucially influences the equilibria. On an important class of graphs, called bipartite graphs, the equilibria do not depend on strategies? payoffs. On certain highly asymmetric graphs, an increase in the payoff of a strategy even decreases the number of agents playing this strategy. In most cases, equilibria do not maximize welfare.