Székely László: Tanglegrams and tanglegram crossing numbers

A tanglegram is a graph, consisting of two rooted binary trees of the same size and a perfect matching joining their leaves. A tanglegram layout is a special straight line drawing of this graph, where the leaves of the trees are placed on two parallel lines, the two trees are drawn as plane trees on either side of the strip created by these lines, and the matching is drawn inside the strip. It is desirable to draw a tanglegram with the least possible number of pairs of crossing edges in the strip. This is the Tanglegram Layout Problem. The minimum number of the crossings obtained in this way is the tanglegram crossing number of the tanglegram. The tanglegram is planar, if it has a layout without crossings. The Tanglegram Layout Problem is NP-hard and is well studied in computer science.
Tanglegrams play a major role in phylogenetics, especially in the theory of coevolution. The first binary tree is the phylogenetic tree of hosts, while the second binary tree is the phylogenetic tree of their parasites, e.g. gopher and louse. The matching connects the host with its parasite. The tanglegram crossing number has been related to the number of times parasites switched hosts.
I present a Kuratowski type characterization of planar tanglegrams and a conjecture for a similar finite characterization of some more general tanglegram crossing number problems. This is a joint work with Eva Czabarka and Stephan Wagner.