Premium
A tanglegram Kuratowski theorem
Author(s) -
Czabarka Éva,
Székely László A.,
Wagner Stephan
Publication year - 2019
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22370
Subject(s) - mathematics , combinatorics , plane (geometry) , matching (statistics) , binary tree , planar , discrete mathematics , geometry , computer science , statistics , computer graphics (images)
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.