Block Crossings in One-Sided Tanglegrams

Abstract Tanglegrams are drawings of two rooted binary phylogenetic trees and a matching between their leaf sets. The trees are drawn crossing-free on opposite sides with their leaf sets facing each other on two vertical lines. Instead of minimizing the number of pairwise edge crossings, we consider the problem of minimizing the number of block crossings , that is, two bundles of edges crossing each other locally. With one tree fixed, the leaves of the second tree can be permuted according to its tree structure. We give a complete picture of the algorithmic complexity of minimizing block crossings in one-sided tanglegrams by showing -completeness, 2.25-approximations, and a fixed-parameter algorithm with the parameter being the number of block crossings of the computed tanglegram. We also state results for non-binary trees.