  Representation languages for coalitional games are a key research area in
algorithmic game theory. There is an inherent tradeoff between how general a
language is, allowing it to capture more elaborate games, and how hard it is
computationally to optimize and solve such games. One prominent such language
is the simple yet expressive Weighted Graph Games (WGGs) representation [14],
which maintains knowledge about synergies between agents in the form of an edge
weighted graph.
  We consider the problem of finding the optimal coalition structure in WGGs.
The agents in such games are vertices in a graph, and the value of a coalition
is the sum of the weights of the edges present between coalition members. The
optimal coalition structure is a partition of the agents to coalitions, that
maximizes the sum of utilities obtained by the coalitions. We show that finding
the optimal coalition structure is not only hard for general graphs, but is
also intractable for restricted families such as planar graphs which are
amenable for many other combinatorial problems. We then provide algorithms with
constant factor approximations for planar, minor-free and bounded degree
graphs.
