  Phylogenetic trees and networks are leaf-labelled graphs used to model
evolution. Display graphs are created by identifying common leaf labels in two
or more phylogenetic trees or networks. The treewidth of such graphs is bounded
as a function of many common dissimilarity measures between phylogenetic trees
and this has been leveraged in fixed parameter tractability results. Here we
further elucidate the properties of display graphs and their interaction with
treewidth. We show that it is NP-hard to recognize display graphs, but that
display graphs of bounded treewidth can be recognized in linear time. Next we
show that if a phylogenetic network displays (i.e. topologically embeds) a
phylogenetic tree, the treewidth of their display graph is bounded by a
function of the treewidth of the original network (and also by various other
parameters). In fact, using a bramble argument we show that this treewidth
bound is sharp up to an additive term of 1. We leverage this bound to give an
FPT algorithm, parameterized by treewidth, for determining whether a network
displays a tree, which is an intensively-studied problem in the field. We
conclude with a discussion on the future use of display graphs and treewidth in
phylogenetics.

Data Structures and Algorithms