Given is a planar undirected connected graph. I am looking for an algorithm to find all connected partitions. A single vertex of a partion is assumed to be connected. Python style preferred.
Example:
For the following connected graph we get $10$ connected partitions:
$1$ partition:
$(1,2,3,4)$
$2$ partitions:
$(0),(1,2,3)$
$(0,1),(2,3)$
$(0,1,2),(3)$
$(0,1,3),(2)$
$3$ partitions:
$(0),(1),(2,3)$
$(0),(2),(1,3)$
$(0,1),(2),(3)$
$(1,2),(0),(3)$
$4$ partitions:
$(0),(1),(2),(3)$
The naive way to do this is to iterate over all partitions of the $V$ vertices, and check the connectedness of each using union-find. Here the number of calls to union-find is the bell number $B_V$, which exhibits faster than exponential growth.
Another "brute-force" method is to iterate over all subsets of the edges, using union-find to get connected components using only these edges. This requires $2^E$ calls to union-find, which in a generic graph is also more than exponential in $V$. However, assuming planarity means $E \leq 3V-6$, so the number of calls to union-find is less than $2^{3V} = 8^V$. This is asymptotically less than $B_V$, but larger than $B_V$ for values of $V$ which are actually tractable for any computer. So I would not recommend it unless your graphs are significantly more sparse than maximal planar. Especially considering that the union-find calls will generally take longer, as they involve more vertices.