Given a oriented planar graph, $G(V,E)$, and a partitioning, $P$ of $V$ into two connected subgraphs of approximately equal orde, I'm trying to create a Markov process to generate other such partitioning $P$. I know I need to worry about the standard distribution and everything, but right now I'm just brainstorming ideas to further pursue.
For this goal, I thought it was natural to imagine defining the partition by weights, and then moving weights these weights along $G$. The partitioning, $P=\{S_1,S_2\}$, could be defined by $\forall v\in S_1, w(v)=1, \forall v \in S_2, w(v)=0$. Below I have some crude ideas for creating functions upon these weights, but am itching to find spectral methods which make life easier, or any other interesting ideas.
By putting a vector field under $G$, you could create a flow network weighted to best reflect the flow of particles along the aforementioned vector field. Here, I could either create disjoint directed cycles, to keep everything nice and discrete, or relax weights to reals and then choose some threshold constant to convert things back to binary. I am aware that similar ideas are used sometimes in fluid dynamics, but have been unable to find useful papers in defining the weights of directed edges.
Another idea is to create a cut $C$ upon $G$, which bisects it, and then define something akin to a dihedral flip. Simply create some bijection between the vertices on the two sides of $C$. However, the bijection should be relatively likely to preserve connected-ness in the induced subgraph defined by the partitioning. Likely, I'd have to restrict myself to restricted kinds of cuts, and then define the bijection in terms of distance either along the edges of $G$, or the cartesian positioning of its orientation. Or maybe the mapping could involve real relaxation as well.
Anyways, I'd be really appreciative of any ideas, this is part of a research project in the fight against gerrymandering!