Optimal Leaf Ordering for Two and a Half Dimensional Phylogenetic Tree Visualisation

Two and a half dimensional graph visualisation is the stacking of a set of related graphs into the third dimension to support visual comparison. A new aesthetic criterion is introduced for the 2 1/2 D visualisation of sets of related phylogenetic trees. This aesthetic requires that the number of crossings between edges linking similar nodes in adjacent trees is minimised allowing a user to easily track the position of a particular species through its lifetime in the stack. We introduce an algorithm for efficiently minimising such crossings and discuss its complexity. Finally, we suggest a new “barrel” layout style which benefits from such crossing minimisation