Abstract:
Tanglegrams are formed by taking two rooted binary trees with the same number of leaves and uniquely matching their leaves. They are usually represented by certain drawings in the plane called layouts. In a layout, the trees are drawn planarly with their leaves facing each other, and the matching between leaves is drawn with straight lines. One problem of interest is the Tanglegram Layout Problem, which is to efficiently find a layout that minimizes the number of crossings. This parallels the Graph Drawing Problem, which attempts to draw a graph in the plane with the fewest number of crossings possible, where one common approach to approximating a solution is to insert edges into a planar subgraph. In this talk, we present a characterization of all planar layouts of a planar tanglegram, which are tanglegrams that have a layout with no crossings. We then discuss applications to the tanglegram analogue of edge insertion for graphs. We conclude with ongoing and future work.
Note: This talk begins with a pre-seminar (aimed at graduate students) at 3:30–4:00. The main talk starts at 4:10.
Join Zoom Meeting: https://washington.zoom.us/j/
Meeting ID: 915 4733 5974