i have a connected planar graph to cut into k parts and want to know how many possible solutions there are. it clearly depends on the shape of the graph since nodes all in a row cannot be partitioned as many ways as the same number of nodes in a bunch.
the stirling number of the second kind gives the number of ways a set can be k-way partitioned, but in this problem the k planar subgraphs have to stay connected, so there are fewer possibilities.
can the question be approached using spectral graph theory and a laplacian matrix?