A tanglegram Kuratowski theorem
Éva Czabarka, Łászló A. Székely, Stephan G. Wagner · Journal of Graph Theory · 2018
Abstract A tanglegram consists of two rooted binary plane trees with the same number of leaves and a perfect matching between the two leaf sets. Tanglegrams are drawn with the leaves on two parallel lines, the trees on either side of the strip created by these lines, and the perfect matching inside the strip. If this can be done without any edges crossing, a tanglegram is called planar. We show that every nonplanar tanglegram contains one of two nonplanar 4‐leaf tanglegrams as an induced subtanglegram, which parallels Kuratowski's Theorem.