Séminaire Lotharingien de Combinatoire, 86B.45 (2022), 12 pp.
Kevin Liu
Planar Tanglegram Layouts and Single Edge Insertion
Abstract.
Tanglegrams are formed by taking two rooted binary trees T and S with the same number of leaves and uniquely matching each leaf in T with a leaf in S. They are usually represented using layouts that embed the trees and matching in the plane. Planar tanglegrams are tanglegrams that have a layout with no crossings. Previous work on planar tanglegrams include enumeration, a Tanglegram Kuratowski Theorem, and an algorithm for drawing a planar layout. In this paper, we characterize all planar layouts of a planar tanglegram. We then apply our work to inserting a single edge into a planar tanglegram.
Received: November 25, 2021.
Accepted: March 4, 2022.
Final version: April 1, 2022.
The following versions are available: