A Study on the Topic of Crossing Minimisation

In this article we undertake a rigorous study on several problems related to the topic of reordering the order of the leaves of a tree according to a specific function and we come up with our own discoveries on the topic. Our study has its roots in tanglegrams, which represent a pair of trees on the same set of leaves with the matching leaves in the two trees joined by an edge. The primary focus of our article is on two distinct approaches for transforming the initial leaf order to match the input order: One Tree Crossing Minimization (OTCM) and One Tree Drawing by Deleting Edges (OTDE). To be more precise, we get a specific order as input and the purpose is to match the initial order of the tree as much as possible with the input order. Both problems are NP Hard, and we present approximation algorithms for each. Moreover, we explore efficient solutions for the isolated case of binary trees. Our own results include providing 3 approximation algorithms for both OTDE and OTCM and displaying that OTDE is hard to approximate within a factor of 4/5 - ∊. Last but not least, we compose a literature survey, studying related topics in the field of crossing minimisation as we compare the solutions and their efficiency with OTDE and OTCM.