A tanglegram Kuratowski theorem. Issue 2 (10th June 2018)

• Record Type: Journal Article
• Authors: Czabarka, Éva; Székely, László A.; Wagner, Stephan
• Is Part Of: Journal of graph theory. Volume 90:Issue 2(2019)
• Page Start: 111
• Page End: 122
• Publication Date: 2018-06-10
• Subjects: crossing number -- graph drawing -- planarity -- subtrees -- tanglegram -- trees -- Primary 05C10; secondary 05C05 -- 05C62 -- 92B10; Graph theory -- Periodicals; 511
• DOI: 10.1002/jgt.22370
• Languages: English
• ISSNs: 0364-9024

Abstract

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.