Date of Award

Spring 2022

Document Type

Open Access Thesis

Department

Mathematics

First Advisor

Eva Czabarka

Abstract

Tanglegrams are graphs consisting of two rooted binary plane trees with the same number of leaves and a perfect matching between the two leaf sets. A Tanglegram drawing is a special way of drawing a Tanglegram; and a Tanglegram is called planar if it has a drawing such that the matching edges do not cross. In this thesis, we will discuss various results related to the construction and planarity of Tanglegrams, as well as demonstrate how to construct all the Tanglegrams of size 4 by looking at two types of rooted binary trees - Caterpillar and Complete Binary Trees. After augmenting a Tanglegram with an edge between its roots, we will prove that the Tanglegram crossing number of the original Tanglegram is greater than or equal to the crossing number of the augmented Tanglegram taken as a graph. We will show that the removal of a matching edge from a Tanglegram of size n ≥3 decreases the Tanglegram crossing number by at most n − 3, and give a family of 1-edge panar Tanglegrams (one for every n ≥3) of size n with Tangle crossing number n − 3, showing that the previous statement is sharp. We will also discuss various conditions on the nonplanarity of Tanglegrams.

Included in

Mathematics Commons

Share

COinS