Characterizing planar tanglegram layouts and applications to edge insertion problems (Q6162140)

Summary: 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. Given the numerous ways to construct a layout, one problem of interest is the Tanglegram Layout Problem, which is to efficiently find a layout that minimizes the number of crossings. This parallels a similar problem involving drawings of graphs, where a common approach is to insert edges into a planar subgraph. In this paper, we explore inserting edges into a planar tanglegram. Previous results on planar tanglegrams include a Kuratowski Theorem, enumeration, and an algorithm for finding a planar layout. We build on these results and characterize all planar layouts of a planar tanglegram. We then apply this characterization to construct a quadratic-time algorithm that inserts a single edge optimally. Finally, we generalize some results to multiple edge insertion.