  A geophylogeny is a phylogenetic tree where each leaf (biological taxon) has
an associated geographic location (site). To clearly visualize a geophylogeny,
the tree is typically represented as a crossing-free drawing next to a map. The
correspondence between the taxa and the sites is either shown with matching
labels on the map (internal labeling) or with leaders that connect each site to
the corresponding leaf of the tree (external labeling). In both cases, a good
order of the leaves is paramount for understanding the association between
sites and taxa. We define several quality measures for internal labeling and
give an efficient algorithm for optimizing them. In contrast, minimizing the
number of leader crossings in an external labeling is NP-hard. We show
nonetheless that optimal solutions can be found in a matter of seconds on
realistic instances using integer linear programming. Finally, we provide
several efficient heuristic algorithms and experimentally show them to be near
optimal on real-world and synthetic instances.
