Title: Treewidth distance on phylogenetic trees,
Abstract: In this article we study the treewidth of the \emph{display graph}, an
auxiliary graph structure obtained from the fusion of phylogenetic (i.e.,
evolutionary) trees at their leaves. Earlier work has shown that the treewidth
of the display graph is bounded if the trees are in some formal sense
topologically similar. Here we further expand upon this relationship. We
analyse a number of reduction rules which are commonly used in the
phylogenetics literature to obtain fixed parameter tractable algorithms. In
some cases (the \emph{subtree} reduction) the reduction rules behave similarly
with respect to treewidth, while others (the \emph{cluster} reduction) behave
very differently, and the behaviour of the \emph{chain reduction} is
particularly intriguing because of its link with graph separators and forbidden
minors. We also show that the gap between treewidth and Tree Bisection and
Reconnect (TBR) distance can be infinitely large, and that unlike, for example,
planar graphs the treewidth of the display graph can be as much as linear in
its number of vertices. On a slightly different note we show that if a display
graph is formed from the fusion of a phylogenetic network and a tree, rather
than from two trees, the treewidth of the display graph is bounded whenever the
tree can be topologically embedded ("displayed") within the network. This opens
the door to the formulation of the display problem in Monadic Second Order
Logic (MSOL). A number of other auxiliary results are given. We conclude with a
discussion and list a number of open problems.