Assume I have $N$ complete graphs $G_1, G_2,...,G_N$, and consider their embeddings $E_1, E_2,...,E_N$ in $\mathbb{R}^2$. Is there a (potentially stochastic) polynomial time algorithm to construct spanning trees $S_1, S_2,...,S_N$ such that the number of intersections between edges from different graphs is minimized (i.e., we want to minimize the number of intersections between edges $e_1 \in S_i$ and $e_2 \in S_j$such that $i \neq j$) ?
