Simultaneous Drawing of Layered Trees

We study the crossing minimization problem in a layered graph drawing of rooted trees whose leaves have a given fixed order on the first layer. The task is to permute the vertices on the other layers to minimize the number of crossings. While this problem is known to be NP-hard for multiple trees even on just two layers, we give a polynomial-time algorithm for the restricted case of two trees. On the other hand, when restricting the number of layers to three, we describe an XP-algorithm in the number of trees.