Complexity of counting all connected subgraphs Let G be a connected graph.


  What is the complexity of counting all connected subgraphs if G is of the following types?
  
  
  G is general.
  G is planar.
  G is bipartite.
  


I don't care about any structures or ..., just need to count all the connected subgraphs!
I'm also interested in the complexity of counting all connected subgraphs with exactly k nodes in G.

Pointers to papers and books are also welcomed!
Welsh states that the problem #P-complete even in the most restricted case (counting the number of connected subgraphs of a planar bipartite graph). See the bottom of page 305 in Welsh, Dominic (1997), "Approximate Counting", Surveys in Combinatorics, Bailey, R. A., ed., Cambridge University Press, pp. 287–324.

In context, though, I wonder whether he really means connected spanning subgraphs. And that leads me to wonder which version of the problem you want: connected spanning subgraphs, connected subgraphs that need not be spanning, or connected induced subgraphs?