i want to find out what small fraction of a solution space a metaheuristic search is actually covering.
this case comes down to the number of possible bipartitions for a non-bipartite, undirected planar graph (it's a political map). the resulting two subgraphs don't need to get exactly half the vertices: any bipartition into two connected subgraphs is a valid solution and i have an objective function to value them.
bipartition is NP-Hard and lots of algorithms and heuristics have been designed to find optimal cases faster. (for example, liption & tarjan showed in the 1970s how to do a particular planar tripartition in linear time.) that's great, but i haven't found any description of the complexity of exhaustively enumerating all bipartition possibilities.
i believe that a bipartition along a planar separator, made of edge cuts which cross the graph, is also exactly a circuit in the graph's dual, at the outer face. if i could count the number of possible circuits at that vertex, i'd know how many ways the graph could be bipartitioned.
does this avenue seem promising? how would the rest of you tackle this question?