Ricerc@Sapienza

We introduce a hybrid metaphor for the visualization of the reconciliations of co-phylogenetic trees, that are mappings among the nodes of two trees. The typical application is the visualization of the co-evolution of hosts and parasites in biology. Our strategy combines a space-filling and a node-link approach. Differently from traditional meth- ods, it guarantees an unambiguous and ‘downward’ representation when- ever the reconciliation is time-consistent (i.e., meaningful). We address the problem of the minimization of the number of crossings in the rep- resentation, by giving a characterization of planar instances and by es- tablishing the complexity of the problem. Finally, we propose heuristics for computing representations with few crossings.