  Simultaneous Embedding with Fixed Edges (SEFE) is a problem where given $k$
planar graphs we ask whether they can be simultaneously embedded so that the
embedding of each graph is planar and common edges are drawn the same. Problems
of SEFE type have inspired questions of Simultaneous Geometrical
Representations and further derivations. Based on this motivation we
investigate the generalization of the simultaneous paradigm on the classical
combinatorial problem of minimum spanning trees. Given $k$ graphs with weighted
edges, such that they have a common intersection, are there minimum spanning
trees of the respective graphs such that they agree on the intersection? We
show that the unweighted case is polynomial-time solvable while the weighted
case is only polynomial-time solvable for $k=2$ and it is NP-complete for
$k\geq 3$.
