Let $G=(V, E)$ be a graph embedded in the plane and let $s, t\in V$ both lie on a common face. Shortest non-crossing $s$-$t$-paths $P$ and $P'$ are shortest paths (wrt. edge count) from $s$ to $t$ that might share some edges, but do not cross, i.e. the one path is always "to the left" (resp. "to the right") of the other.
Sample a collection $P_1, ..., P_k$ of shortest pairwise non-crossing $s$-$t$-paths in $G$ uniformly at random.
Is this possible in polynomial time, assuming that uniform sampling from $[0, 1]$ is given in $\mathcal{O}(1)$?
One attempt might be: Assign lexicographic weights $w_i: E\to \{1\}\times [0, 1]$ independently for each edge and $i=1,...,k$ uniformly at random. Then find a collection of non-crossing $s$-$t$-paths $P_1, ..., P_k$ with minimum total weight $w_1(P_1)+...+w_k(P_k)$. This solves the above mentioned sampling problem. While one can find in the literature polynomial algorithms for $k$ non-crossing-paths (for arbitrary source-sink-pairs), they assume the same weights for all $k$ paths.
Any help is appreciated.