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.
Rights
© 2022, Drew Joseph Scalzo
Recommended Citation
Scalzo, D. J.(2022). Tangled up in Tanglegrams. (Master's thesis). Retrieved from https://scholarcommons.sc.edu/etd/6821