An h-cluster in a graph is a set of h vertices which maximizes the number of edges in the graph induced by these vertices. We show that the connected h-cluster problem is NP-complete on planar graphs.
