xxx 00000 Jonathan Klawitter was supported by the Beyond Prediction Data
Science Research Programme (MBIE grant UOAX1932). Thomas C. van Dijk was
partially supported by the DFG grant Di 2161/2-1. A preliminary version of
this paper appeared in the proceedings of the 12th International Conference on
Geographic Information Science (GIScience 2023) [31]. Implementations of the
algorithms and the experiments are available online at
github.com/joklawitter/geophylo. [first]Jonathan
<EMAIL_ADDRESS>[second]Felix
<EMAIL_ADDRESS>[third]Thomas
C. van Dijk0000-0001-6553-7317 first]University of Auckland, New Zealand
second]Universität Würzburg, Germany third]Ruhr-Universität Bochum, Germany J.
Klawitter et al. Visualizing Geophylogenies

# Visualizing Geophylogenies – Internal and External Labeling with
Phylogenetic Tree Constraints

Joris Y. Scholl  Alexander Zaft  [  [  [

###### Abstract

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. On the positive side, we show that crossing-free instances can be
solved in polynomial time and give a fixed-parameter tractable (FPT)
algorithm. Furthermore, 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.

##  1 Introduction

A _phylogeny_ describes the evolutionary history and relationships of a set of
taxa such as species, populations, or individual organisms [42]. It is one of
the main tasks in phylogenetics to infer a phylogeny for some given data and a
particular model. Most often, a phylogeny is modelled and visualized with a
_rooted binary phylogenetic tree_ $T$, that is, a rooted binary tree $T$ where
the leaves are bijectively labeled with a set of $n$ taxa. For example, the
phylogenetic tree in Fig. 1(a) shows the evolutionary species tree of the five
present-day kiwi (Apteryx) species. The tree is conventionally drawn with all
edges directed downwards to the leaves and without crossings (_downward
planar_). There exist several other models for phylogenies such as the more
general phylogenetic networks which can additionally model reticulation events
such as horizontal gene transfer and hybridization [25], and unrooted
phylogenetic trees, which only model the relatedness of the taxa [42]. Here we
only consider rooted binary phylogenetic trees and refer to them simply as
phylogenetic trees.

In the field of phylogeography, geographic data is used in addition to the
genetic data to improve the inference of the phylogeny. We may thus have
spatial data associated with each taxon of a phylogenetic tree such as the
distribution range of each species or the sampling site of each voucher
specimen used in a phylogenetic analysis. For example, Fig. 1(b) shows the
distributions of the kiwi species from Fig. 1(a). We speak of a _geophylogeny_
(or _phylogeographic tree_) if we have a phylogenetic tree $T$, a map $R$, and
a set $P$ of features on $R$ that contains one feature per taxon of $T$; see
Fig. 1(c) for a geophylogeny of the kiwi species. In this paper, we focus on
the case where each element $x$ of $P$ is a point, called a _site_ , on $R$,
and only briefly discuss the cases where $x$ is a region, or a set of points
or regions.

(a) Rooted binary phylogenetic tree.

(b) Map with the distribution of each species shown.

(c) Visualization of the geophylogeny.

Figure 1: To visualize this geophylogeny of the five present-day kiwi species
(Tokoeka/South Island Brown Kiwi – Apteryx australis, Rowi/Okarito Brown Kiwi
– A. rowi, North Island Brown Kiwi – A. mantelli, Great Spotted Kiwi – A.
haastii, Little Spotted Kiwi – A. owenii), we combine the phylogenetic tree
(a) together with the distribution map (b) into a single figure (c). To this
end, we may pick a rotation of the map and a placement of the tree as well as
a leaf order that facilities easy association based on the colors between the
leaves and the features on the map. (Phylogeny and map inspired by Weir et al.
[45].)

#### Visualizing Geophylogenies.

When visualizing a geophylogeny, we may want to display its tree and its map
together in order to show the connections (or the non-connections) between the
leaves and the sites. For example, we may want to show that the taxa of a
certain subtree are confined to a particular region of the map or that they
are widely scattered. In the literature, we mainly find three types of
drawings of geophylogenies that fall into two composition categories [27, 22].
In a _side-by-side (juxtaposition)_ drawing, the tree is drawn planar directly
next to the map. To show the correspondences between the taxa and their sites,
the sites on the maps are either labeled or color coded (as in Fig. 2(a) and
Fig. 1(c), respectively), or the sites are connected with _leaders_ to the
leaves of the tree (as in Fig. 2(b)). We call this _internal labeling_ and
_external labeling_ , respectively. There also exist _overlay
(superimposition)_ illustrations where the phylogenetic tree is drawn onto the
map in 2D or 3D with the leaves positioned at the sites [47, 29, 41]; see Fig.
3. While the association between the leaves and the sites is obvious in
overlay illustrations, Page [36] points out that the tree and, in particular,
the tree heights might be hard to interpret.

(a) Internal labeling with labels and colors [8].

(b) External labeling with s-leaders [26].

Figure 2: Side-by-side drawings of geophylogenies from the literature.

(a) 2D overlay drawing of a geophylogeny by Xia [47].

(b) 3D overlay drawing of a geophylogeny by Kidd and Liu [29].

Figure 3: Overlay drawings of geophylogenies from the literature.

Drawing a geophylogeny involves various subtasks, such as choosing an
orientation for the map, a position for the tree, and the placement of the
labels. Several existing tools support drawing geophylogenies [39, 38, 41, 36,
14], but we suspect that in practice many drawings are made “by hand”. The
tools GenGIS by Parks et al. [39, 38], a tool by Page [36], and the R-package
phytools by Revell [41] can generate side-by-side drawings with external
labeling. The former two try to minimize leader crossings by testing random
leaf orders and by rotating the phylogenetic tree around the map; Revell uses
a greedy algorithm to minimize leader crossings. The R package phylogeo by
Charlop-Powers and Brady [14] uses internal labeling via colors.
Unfortunately, none of the articles describing these tools formally define a
quality measure being optimized or studies the underlying combinatorial
optimization problem from an algorithmic perspective. In this paper, we
introduce a simple combinatorial definition for side-by-side drawings of
geophylogenies and propose several quality measures (Section 2).

#### Labeling Geophylogenies.

The problem of finding optimal drawings of geophylogenies can be considered a
special case of map labeling. In this area, the term _labeling_ refers to the
process of annotating _features_ such as points (sites), lines, or regions in
maps, diagrams, and technical drawings with labels [7]. This facilitates that
users understand what they see. As with geophylogenies, _internal labeling_
places the labels inside or in the direct vicinity of a feature; _external
labeling_ places the labels in the margin next to the map and a label is then
connected to the corresponding feature with a _leader_. An _s -leader_ is
drawn using a single (straight) line segment as in Figs. 2(b) and 4(b).
Alternatively, a _po -leader_ (for: parallel, orthogonal) consists of a
horizontal segment at the site and a vertical segment at the leaf, assuming
the the labels are above the drawing; see Fig. 4(c). In the literature, we
have only encountered s-leaders in geophylogeny drawings, but argue below that
po-leaders should be considered as well. In a user study on external labeling,
Barth, Gemsa, Niedermann, and Nöllenburg [3] showed that s-leaders perform
well when users are asked to associate sites with their labels and vice versa,
but that po-leaders (and “diagonal, orthogonal” do-leaders) are among the
aesthetic preferences. We thus consider drawings of geophylogenies that use
external labeling with s\- and po-leaders.

For internal labeling, a common optimization approach is to place the most
labels possible such that none overlap; see Neyer [34] for a survey on this
topic. Existing algorithms can be applied to label the sites in a geophylogeny
drawing and it is geometrically straight-forward to place the labels for the
leaves of $T$. However, a map reader must also be aided in associating the
sites on the map with the leaves at the border based on these labels (and
potentially colors). Consider the drawing in Fig. 1(c), which uses color-based
internal labeling: the three kiwi species _A. australis_ , _A. rowi_ , and _A.
mantelli_ occur in this order from South to North. When using internal
labeling, we would thus prefer, if possible, to have the three species in this
order in the tree as well – as opposed to their order in Fig. 1(a).

External labeling styles conventionally forbid crossing the leaders as such
crossings could be visually confusing (cf. Fig. 2(b)). Often the total length
of leaders is minimized given this constraint. See Bekos, Niedermann, and
Nöllenburg [7] for an extensive survey on external labeling techniques.
External labeling for geophylogenies is closely related to many-to-one
external labeling, where a label can be connected to multiple features. In
that case one typically seeks a placement that minimizes the number of
crossings between leaders, which is an NP-hard problem [33]. The problem
remains NP-hard even when leaders can share segments, so-called hyper-leaders
[4]. Even though our drawings of geophylogenies have only a one-to-one
correspondence, the planarity constraint on the drawing of the tree restricts
which leaf orders are possible and it is not always possible to have crossing-
free leaders in a geophylogeny. In order to obtain a drawing with low visual
complexity, our task is thus to find a leaf order that minimizes the number of
leader crossings.

#### Further Related Work.

Since there exists a huge variety of different phylogenetic trees and
networks, it is no surprise that a panoply of software to draw phylogenies has
been developed [24, 40, 1]. Here we want to mention DensiTree by Bouckaert
[10]. It draws multiple phylogenetic trees on top of each other for easy
comparison in so-called cloudograms and, relevantly to us, has a feature to
extend its drawing with a map for geophylogenies. Furthermore, the theoretical
study of drawings of phylogenies is an active research area [17, 16, 2, 23, 9,
12, 44, 32, 30]. In many of these graph drawing problems, the goal is to find
a leaf order such that the drawing becomes optimal in a certain sense. This is
also the case for _tanglegrams_ , where two phylogenetic trees on the same
taxa are drawn opposite each other (say, one upward and one downward planar).
Pairs of leaves with the same taxon are then connected with straight-line
segments and the goal is to minimize the number of crossings [11]. This
problem is NP-hard if the leaf orders of both trees are variable, but can be
solved efficiently when one side is fixed [19]. The latter problem is called
the One-Sided Tanglegram problem and we make use of the efficient algorithm by
Fernau et al. [19] later on.

#### Results and Contribution.

We formalize several graph visualization problems in the context of drawing
geophylogenies. We propose quality measures for drawings with internal
labeling and show that optimal solutions can be computed in quadratic time
(Section 3). For external labeling (Section 4), we prove that although
crossing minimization of s\- and po-leaders is NP-hard in general, it is
possible to check in polynomial time if a crossing-free drawing exists.
Moreover, we give a fixed-parameter tractable (FPT) algorithm and show that
there exist instances with practical relevance that can be solved efficiently
by the FPT algorithm. Furthermore, we introduce an integer linear program
(ILP) and several heuristics for crossing minimisation. We evaluate these
solutions on synthetic and real-world examples, and find that the ILP can
solve realistic instances optimally in a matter of seconds and that the
heuristics, which run in a fraction of a second, are often (near-)optimal as
well (Section 5). We close the paper with a discussion and open problems.

##  2 Definitions and Notation

For a phylogenetic tree $T$, let $V(T)$ be its vertex set, $E(T)$ its edge
set, $L(T)$ its leaves, and $I(T)$ its internal vertices. As size of an
instance we let $n=\lvert L(T)\rvert$ be the number of leaves. For an internal
vertex $v$ of $T$, let $T(v)$ be the subtree rooted at $v$ and $n(v)=\lvert
L(T(v))\rvert$. The _clade_ of $v$ is $L(T(V))$, i.e. the set of leaves in the
subtree rooted at $v$. A _cherry_ of $T$ is a subtree of $T$ on exactly two
leaves that have the same parent.

A _map_ $R$ is an axis-aligned rectangle and a _site_ is a point on $R$. A
_geophylogeny_ $G$ consists of a phylogenetic tree $T(G)$, a map $R(G)$, a set
of point $P(G)$ on $R(G)$ as well as a 1-to-1 mapping between $L(T(G))$ and
$P(G)$. Call the elements of $L(T(G))=\\{\ell_{1},\ldots,\ell_{n}\\}$ and
$P(G)=\\{p_{1},\ldots,p_{n}\\}$ so that without loss of generality the mapping
is given by the indices, that is, $\ell_{i}\leftrightarrow p_{i}$, for
$i\in\\{1,\ldots,n\\}$. For further ease of notation, we only write $T$, $R$,
and $P$ instead of $T(G)$, $R(G)$, and $P(G)$, respectively, if $G$ clear from
context.

We define a _drawing_ $\Gamma$ of $G$ as consisting of drawings of $R$ with
$P$ and $T$ in the plane with the following properties; see Fig. 4. We assume
that $T$ is always drawn at a fixed position above $R$ such that the leaves of
$T$ lie at evenly spaced _positions_ on the upper boundary of $R$.
Furthermore, we require that $T$ is drawn _downward planar_ , that is, all
edges of $T$ point downwards from the root towards the leaves, and no two
edges of $T$ cross. (In our examples we draw $T$ as a “rectangular cladogram”,
but the exact drawing style is irrelevant given downward planarity.) The
points of $P$ are marked on $R$ and the drawing uses either internal labeling
as in Fig. 4(a) or external labeling with s\- or po-leaders as in Figs. 4(b)
and 4(c). For drawings with external labeling, we let $s_{i}$ denote the
leader that connects $\ell_{i}$ and $p_{i}$. (We ignore the leaf labels as
they do not effect the combinatorics: they can simply be added in a post-
processing step where $T$ can be moved upwards to create the necessary space.)

Since the tree is drawn without crossings and the sites have fixed locations,
the only combinatorial freedom in the drawing $\Gamma$ is the embedding of
$T$, i.e.w̃hich child is to the left and which is to the right. Furthermore,
since we fixed the relative positions of the map and the leaves, note that
there is also no “non-combinatorial” freedom. Hence, an embedding of $T$
corresponds one-to-one with a left-to-right order of $L(T)$ and we call this
the _leaf order_ $\pi$ of $\Gamma$. For example, if a leaf $\ell_{i}$ is at
position 4 in $\Gamma$, then $\pi(\ell_{i})=4$. Further, let
$\operatorname{\text{x}}(v)$ and $\operatorname{\text{y}}(v)$ denote the x-
and y-coordinate, respectively, of a site or leaf $v$ of $T$ in $\Gamma$. In a
slight abuse of notation, we also call it a drawing of geophylogeny even when
the leaf order has not been fixed yet.

(a) Drawing of $G$ with internal labeling, … (b) …with s-leaders and 1
crossing, … (c) …and with po-leaders and 0 crossings.

Figure 4: In a drawing of a geophylogeny $G$, we place $T$ above $R$ and use
either internal or external labeling to show the mapping between $P$ and
$L(T)$. Figures (b) and (c) minimize the number of crossings for their leader
type. Note the difference in embedding of $T$ and that not all permutations of
leaves are possible.

##  3 Geophylogenies with Internal Labeling

In this section, we consider drawings of geophylogenies with internal
labeling. While these drawings trivially have zero crossings – there are no
leaders – a good order of the leaves is still crucial, since it can help the
reader associate between $L(T)$ and $P$. It is in general not obvious how to
determine which leaf order is best for this purpose; we propose three quality
measures and a general class of measures that subsume them. Any measure in
this class can be efficiently optimized by the algorithm described below. In
practice one can easily try several quality measures and pick whichever suits
the particular drawing; a user study of practical readability could also be
fruitful.

#### Quality Measures.

When visually searching for the site $p_{i}$ corresponding to a leaf
$\ell_{i}$ (or the opposite direction), it is seems beneficial if $\ell_{i}$
and $p_{i}$ are close together. Our first quality measure, _Distance_ , sums
the Euclidean distances of all pairs $(p_{i},\ell_{i})$; see Fig. 5(a).

Since the tree organizes the leaves from left to right along the top of the
map, and especially if the distance of pairs $\ell_{i}$ and $p_{i}$ is
dominated by the vertical component as in Fig. 2(b), it might be better to
consider only the horizontal distances, i.e.
$\sum_{i=1}^{n}\lvert\operatorname{\text{x}}(p_{i})-\operatorname{\text{x}}(\ell_{i})\rvert$,
which we call _XOffset_ ; see Fig. 5(b).

Finally, instead of the geometric offset, _IndexOffset_ considers how much the
leaf order permutes the geographic left to right order of the sites. Assuming
without loss of generality that the sites are in general position and indexed
from left to right, we sum how many places each leaf $\ell_{i}$ is away from
leaf position $i$, i.e. $\sum_{i=1}^{n}\lvert\pi(\ell_{i})-i\rvert$; see Fig.
5(c).

These measures have in common that they sum over some “quality” of the leaves,
where the quality of a leaf depends only on its own position and that of the
sites (but not the other leaves). We call such quality measures _leaf
additive_. Unfortunately not all sensible quality measures are leaf additive
(such as for example the number of inversions in $\pi$).

(a) Distance – sum of Euclidean distances.

(b) XOffset – sum of horizontal distances.

(c) IndexOffset – sum of position shifts, here 4.

Figure 5: Orange arrows indicate what the three quality measures for internal
labeling consider.

#### Algorithm for Leaf-Additive Quality Measures.

Let $f\colon L(T)\times\\{1,\ldots,n\\}\to\mathbb{R}$ be a quality measure for
placing one particular leaf at a particular position; the location of the
sites is constant for a given instance, so we do not consider it an argument
of $f$. This uniquely defines a leaf additive objective function on drawings
by summing over the leaves; assume without loss of generality that we want to
minimize this sum.

Now we naturally lift $f$ to inner vertices of $T$ by taking the sum over
leaves in the subtree rooted at that vertex – in the best embedding of that
subtree. More concretely, note that any drawing places the leaves of any
subtree at consecutive positions and they take up a fixed width regardless of
the embedding. Let $F(v,i)$ be the minimum, taken over all embeddings of
$T(v)$ and assuming the leftmost leaf is placed at position $i$, of the sum of
quality of the leaves of $T(v)$. Then by definition the optimal objective
value for the entire instance is $F(w,1)$, where $w$ is the root of $T$.

######  Theorem 3.1.

Let $G$ be a geophylogeny with $n$ taxa and let $f$ be a leaf additive
objective function. A drawing $\Gamma$ with internal labeling of $G$ that
minimizes (or maximizes) $f$ can be computed in $\mathcal{O}(n^{2})$ time.

######  Proof 3.2.

For an inner vertex $v$ with children $x$ and $y$, we observe the following
equality, since the embedding has only two ways of ordering the children and
those subtrees are then independent; see also Fig. 6:

$F(v,i)=\min\\{\quad F(x,i)+F(y,i+n(x)),\quad F(y,i)+F(x,i+n(y))\quad\\}$ (1)

Using dynamic programming on $F$, for example in postorder over $T$, allows us
to calculate $F(\rho,1)$ in $\mathcal{O}(n^{2})$ time and space, since there
are $2n$ vertices, $n$ possible leaf positions, and Eq. 1 can be evaluated in
constant time by precomputing all $n(v)$. As is typical, the optimal embedding
of $T$ can be traced back through the dynamic programming table in the same
running time.

(a) $F(v,1)=\min\\{3,4\\}=3$

(b) $F(v,2)=\min\\{1,5\\}=1$

Figure 6: Computing IndexOffset for the subtree $T(v)$ at positions $1$ and
$2$.

#### Adaptability.

Note that we can still define leaf additive quality measures when $P$ contains
regions (rather than just points) as in Fig. 1. For example, instead of
considering the distance between $\ell_{i}$ and $p_{i}$, we could consider the
smallest distance between $\ell_{i}$ and any point in the region $p_{i}$.
Similarly, if each element of $P$ is a set of sites, we could use the average
or median distance to the sites corresponding to $\ell_{i}$. For such a leaf
additive quality measure $f$, our algorithm fins an optimal leaf order in
$\mathcal{O}(n^{2}x)$ time where $x$ is a bound on the time needed to compute
$f(\ell_{i},j)$ over all $i,j\in\\{1,\ldots,n\\}$.

#### Interactivity.

With the above algorithm, we can restrict leaves and subtrees to be in a
certain position or a range of positions, simply by marking all other
positions as prohibitively expensive in $F$; the rotation of an inner vertex
can also be fixed by considering only the corresponding term of Eq. 1. This
can be used if there is a conventional order for some taxa or to ensure that
an outgroup-taxon (i.e. taxon only included to root and calibrate the
phylogenetic tree) is placed at the leftmost or rightmost position.
Furthermore, this enables an interactive editing experience where a designer
can inspect the initial optimized drawing and receive re-optimized versions
based on their feedback – for example “put the leaves for the sea lions only
where there is water on the edge of the map”. (This is leaf additive.)

##  4 Geophylogenies with External Labeling

In this section, we consider drawings of geophylogenies that use external
labeling. Recall that for a drawing $\Gamma$ of a given geophylogeny $G$, we
want to find a leaf order $\pi$ such that the number of leader crossings in
$\Gamma$ is minimized. We show the following.

  1. 1.

The problem is NP-hard in general.

  2. 2.

A crossing-free solution can be found in polynomial time if it exists.

  3. 3.

Some instances have a geometric structure that allows us to compute optimal
solutions in polynomial time.

  4. 4.

The problem is fixed parameter tractable (FPT) in a parameter based on this
structure.

  5. 5.

We give an integer linear program (ILP) to solve the problem.

  6. 6.

We give several heuristic algorithms for the problem.

All results hold analogously for s\- and po-leaders; only the parameter value
of the FPT algorithm is different depending on the leader type.

###  4.1 NP-Hardness

In order to prove that the decision variant of our crossing minimization
problem is NP-complete, we use a reduction from the classic Max-Cut problem,
which is known to be NP-complete [20]. In an instance of Max-Cut, we are given
a graph $G$ and a positive integer $c$, and have to decide if there exists a
bipartition $(A,B)$ of $V$ such that at least $c$ edges have one endpoint in
$A$ and one endpoint in $B$; see Fig. 7. The proof of the following theorem is
inspired by the construction Bekos et al. [4] use to show NP-completeness of
crossing-minimal labeling with hyperleaders (with a reduction from Fixed
Linear Crossing Number).

Figure 7: This partition of the triangle $v_{1}v_{2}v_{3}$ cuts the two edges
$\\{v_{1},v_{2}\\}$, $\\{v_{2},v_{3}\\}$.

######  Theorem 4.1.

Let $G$ be a geophylogeny and $k$ a positive integer. For both s\- and po-
leaders, deciding whether a drawing $\Gamma$ of $G$ with external labeling
admits a leaf order $\pi$ that induces at most $k$ leader crossings is NP-
complete.

######  Proof 4.2.

The problem is in NP since, given $G$, $k$, and $\pi$, we can check in
polynomial time whether this yields at most $k$ crossings. To prove NP-
hardness, we use a reduction from Max-Cut as follows. The proof works the same
for s\- and po-leaders; we use po-leaders in the figures.

For an instance $(G,c)$ of Max-Cut, we construct an instance of our leader
crossing minimisation problem by devising a geophylogeny $G$ with phylogenetic
tree $T$, points $P$ on a map $R$ and a constant $k$; see Fig. 8. Without loss
of generality, we assume that each vertex in $G$ has at least degree 2. Let
$V(G)=\\{v_{1},\ldots,v_{n}\\}$ and $m=\lvert E(G)\rvert$. We consider each
edge $\\{v_{i},v_{j}\\}$ with $i<j$ to be directed as $v_{i}v_{j}$. Let $E(G)$
be ordered $e_{1},\ldots,e_{m}$ lexicographically on the indices $i$ and $j$.
Throughout the following, let $(A,B)$ be some partition of $V(G)$ and let $R$
have height $4m+4+d$ where we set $d$ appropriately below.

We first describe the broad structure of the reduction and then give details
on the specific gadgets. Each vertex is represented by a _vertex gadget_ in
$T$. For each edge $v_{i}v_{j}$ in $E(G)$, there is an _edge gadget_ that
connects sites on the map to the vertex gadgets with four leaders. Using
_fixing gadgets_ to restrict the possible positions for vertex gadget’s
leaves, we enforce that an edge gadget induces 2 crossing if $v_{i}$ and
$v_{j}$ are both in $A$ or both in $B$; otherwise it will induce 1 crossing.
The number of crossings between leaders of different edge gadgets is in total
some constant $k_{\text{fix}}$. We set $k=k_{\text{fix}}+2m-c$. Consequently,
if $\langle T,R,P\rangle$ admits a drawing with at most $k$ leader crossings,
then $G$ admits a cut with at least $c$ edges, and vice versa.

Figure 8: Sketch of the reduction of the graph from Fig. 7 to a geophylogeny
drawing with po-leaders. We simplified $v_{i}$ to $i$; each edge gadget is
drawn in the respective color; fixing gadgets are represented by triangles in
the tree and hatched rectangles on the map.

#### Vertex Gadgets.

Each vertex $v_{i}\in V(G)$ is represented by two subtrees rooted at vertices
$i$ and $i^{\prime}$ in $T$ such that from $i$ going two edges up and one down
we reach $i^{\prime}$. In $T(i)$ there is a leaf labeled $ij$ for each edge
$v_{i}v_{j}$ or $v_{j}v_{i}$ incident to $v_{i}$ in $G$. Furthermore, $T(i)$
has a planar embedding where the leaves can be in increasing (or decreasing)
order based on the order of the corresponding edges in $E(G)$; see again Fig.
8. $T(i^{\prime})$ is built analogously, though we label the leaves with
$ij^{\prime}$. In $T$, the vertex gadgets and fixing gadgets alternate; more
precisely, the subtree of a central fixing gadget lies inside the subtree of
the vertex gadget for $v_{1}$, which in turn lies in the subtree of a fixing
gadget, and so on. The fixing gadgets ensure that either $T(i)$ is in the left
half of the drawing and $T(i^{\prime})$ in the right half, or vice versa
(explained below). Furthermore, we interpret $T(i)$ being in the left (right)
half as $v_{i}$ being in $A$ (resp. $B$).

#### Edge Gadgets.

For an edge $e_{h}=v_{i}v_{j}\in E(G)$, we have four sites $ij$, $ji$,
$ij^{\prime}$, $ji^{\prime}$ on the central axis of the drawing, which
correspond to the leaves in $T(i)$, $T(j)$, $T(i^{\prime})$, $T(j^{\prime})$
with the same label. From bottom to top, we place the sites $ij$ and $ji$ at
heights $2h-1$ and $2h$, respectively; we place the sites $ij^{\prime}$ and
$ji^{\prime}$ at $4m-2(h-1)-1$ and $4m-2(h-1)$, respectively; see Fig. 9.
Hence, in the bottom half the sites are placed in the order of the edges,
while in the top half they are (as pairs) in reverse order. Note that while
the order of the sites $ij$, $ji$, $ij^{\prime}$, $ji^{\prime}$ is fixed, the
order of the leaves $ij$, $ji$, $ij^{\prime}$, $ji^{\prime}$ is not. Yet there
are only four possible orders corresponding to whether $v_{i}$ and $v_{j}$ are
in $A$ or $B$. Further note that whether the leaders of the edge gadget cross
is therefore not based on the geometry or the type of the leaders but solely
on the leaf order. In particular, if $v_{i}v_{j}$ is cut by $(A,B)$ (as in
Fig. 9(a)), then we have the leaf order $ji^{\prime}$, $ij$, $ij^{\prime}$,
$ji$ with $ji^{\prime}$ and $ij$ left of the centre (up to reversal of the
order). Therefore the leaders $s_{ij}$ and $s_{ji^{\prime}}$ cross while
$s_{ij^{\prime}}$ and $s_{ji}$ do not. Hence, there is exactly one crossing.
On the other hand, if $v_{i}v_{j}$ is not cut by $(A,B)$ (as in Fig. 9(b)),
then we have the leaf order $ij$, $ji$, $ij^{\prime}$, $ji^{\prime}$ with $ij$
and $ji$ left of the centre (up to reversal of the order). Hence we have two
crossings as both $s_{ij}$ and $s_{ji}$ as well as $s_{ij^{\prime}}$ and
$s_{ji^{\prime}}$ cross.

(a) If $v_{1}v_{2}$ is in the cut, its edge gadget induces exactly 1 crossing.

(b) If $v_{1}v_{2}$ is not in the cut, its edge gadget induces exactly 2
crossing.

Figure 9: The edge gadget for $v_{1}v_{2}$ connects the vertex gadgets for
$v_{i}$ and $v_{j}$.

#### Edge Pairs.

Let $v_{i}v_{j},v_{k}v_{l}\in E(G)$. We assume an optimal leaf order in each
vertex gadget. Then careful examination of the overall possible leaf orders
(and partitions) shows that the leaders in the edge gadgets of $v_{i}v_{j}$
and $v_{k}v_{l}$ induce exactly three crossings if $v_{i}v_{j}$ and
$v_{k}v_{l}$ share a vertex; see again Fig. 8. If the two edges are disjoint,
then the leaders induce exactly four crossings; see Fig. 10. Note that
changing the partition or the order of vertices does not change the number of
crossings; it only changes which pairs among the eight leaders cross. We can
thus set $k_{\text{fix}}$ as three times the number of adjacent edge pairs
plus four times the number of disjoint edge pairs.

Figure 10: Leaders for two edge gadgets of disjoint edges induce four
crossings.

#### Fixing Gadgets.

To ensure that the two subtrees of each vertex gadget are distributed to the
left and to the right, we add a fixing gadget in the center and one after each
position allocated to a vertex gadget subtree. If both subtrees of a vertex
gadget would be placed on the same side of a fixing gadget, then the fixing
gadget would have to be translated and induce too many crossings. More
precisely, each fixing gadget is composed of a series of _fixing units_. A
fixing unit $F$ consists of a four-leaf tree with cherries
$\\{a,a^{\prime}\\}$ and $\\{b,b^{\prime}\\}$. Assuming $F$ is to be centered
at position $x$, we place the sites for $a$ and $a^{\prime}$ (for $b$ and
$b^{\prime}$) at $x$ at height $4m+d+$ 1 and 4 (resp. plus 2 and 3),
respectively. Thus if $F$ is centred at $x$, it can be drawn with 0 crossings;
see Fig. 11(a). However, if $F$ is translated by two or more then it induces 2
crossings; see Fig. 11(b). Since each vertex of $G$ has at least degree two,
the two trees $T(i)$ and $T(i^{\prime})$ of a vertex gadget have at least two
leaves each. Hence, $F$ cannot be translated by just one position. By using
$m-c$ fixing units per fixing gadget, it becomes too costly to move even one
fixing gadget as the instance would immediately have to many crossings.
Finally, we set $d$ such that no leader of an edge gadget can cross a leader
of a fixing gadget. In particular, $d=4$ is sufficient for po-leaders, but we
might need a larger $d$ for s-leaders.

(a) A fixing gadget at its designated place induces zero crossings.

(b) A fixing gadget translated by at least two induces $2$ crossings per
fixing unit.

Figure 11: A fixing gadget consists of a series of four-leaf fixing units and
is always placed at its designed place since it would otherwise cause too many
crossings.

###  4.2 Crossing-Free Instances

We now show how to decide whether a geophylogeny admits a drawing without
leader crossings in polynomial time for both s\- and po-leaders.

######  Proposition 4.3.

Let $G$ be a geophylogeny on $n$ taxa. For both s\- and po-leaders, we can
decide if a drawing $\Gamma$ of $G$ with external labeling admits a leaf order
$\pi$ that induces zero leader crossings in $\mathcal{O}(n^{6})$ time.

######  Proof 4.4.

To find a leaf order $\pi$ for $\Gamma$ that induces zero leader crossings, if
it exists, we use a dynamic program similar to the one we used for internal
labeling in Theorem 3.1. Let $i\in\\{1,\ldots,n\\}$ and let $v\in V(T)$. Then
we store in $F(v,i)$ up to $n(v)$ embeddings of $T(v)$ for which $T(v)$ can be
placed with its leftmost leaf at position $i$ such that the leaders to $T(v)$
are pairwise crossing free. Note that $F(v,i)$ always stores exactly one
embedding when $v$ is a leaf. For an inner vertex $v$ with children $x$ and
$y$, we combine pairs of stored embeddings of $T(x)$ and $T(y)$ and test
whether they result in a crossing free embedding of $T(v)$. For $\rho$ the
root of $T$, we get a suitable $\pi$ for each embedding stored in $F(\rho,1)$.
However, since combining embeddings of $T(x)$ and $T(y)$ can result in
$\mathcal{O}(n(v)^{2})$ many embeddings of $T(v)$, we have to be more
selective. We now describe when we have to keep multiple embeddings of $T(v)$,
how we select them, and show that at most $n(v)$ embeddings for $T(v)$ at
position $i$ suffice. We first describe the details for s-leaders and then for
po-leaders.

####  s-Leaders.

Suppose that we can combine an embedding of $T(x)$ and an embedding of $T(y)$
where $T(v)$ is placed with its leftmost leaf at position $i$ such that the
leaders of $T(v)$ pairwise do not cross. Consider the set $P(v)$ of sites
corresponding to $L(T(v))$. In particular, let $p_{k}$ have the lowest
y-coordinate among the sites in $P(v)$. Let $H(v,i)$ be the convex hull of the
sites $P(v)$ and the leaf positions $i$ and $i+n(v)-1$; see Fig. 12. We
distinguish three cases:

  1. Case 1 -

there is no site of $P\setminus P(v)$ inside $H(v,i)$: Then no leader of a
site $p_{o}\in P\setminus P(v)$ has to “leave” $H(v,i)$. A leader that would
need to intersect $H(v,i)$ would cause a crossing with a leader of $T(v)$ for
any embedding of $T(v)$. Hence it suffices to store only this one embedding of
$T(v)$ and not consider any further embeddings.

  2. Case 2 -

there is a site $p_{o}\in P\setminus P(v)$ trapped in $H(v,i)$: More
precisely, let $H(v,i,p_{o})$ be the convex hull of the positions $i$ and
$i+n(v)-1$ and all sites of $P(v)$ above $p_{o}$. We consider $p_{0}$
_trapped_ if the leader of $p_{0}$ cannot reach any position left of $i$ or
right of $i+n(v)-1$ without crossing $H(v,i,p_{o})$; see Fig. 12(a). Hence we
would definitely get a crossing for this embedding of $T(v)$ later on and thus
reject it immediately.

  3. Case 3 -

there is a site $p_{o}\in P\setminus P(v)$ but not trapped inside $H(v,i)$:
Suppose that the leader $s_{o}$ of $p_{o}$ can reach positions
$j_{1},\ldots,j_{k_{o}}$ without intersecting $H(v,i,p_{o})$. Consider the
leader $s_{k}$ of $p_{k}$ for the current embedding of $T(v)$. Note that
$s_{k}$ prevents $s_{o}$ from reaching either any position to the left of $i$
or to the right of $i+n(v)-1$; see Fig. 12(b). If this means that $s_{k}$
cannot reach any position, then we reject the embedding. Otherwise we would
want to store this embedding of $T(v)$ and an embedding of $T(v)$ where
$s_{k}$ can reach a position on the other side (if it exists). However, we
have to consider all other sites in $H(v,i)$, which we do as follows.

(a) The non-$T(v)$ site $p_{o}$ inside $H(v,i)$ may connect only to a position
far to the right.

(b) The leader of the non-$T(v)$ site $p_{o}$ inside $H(v,i)$ can reach
positions to the left of position $i$.

(c) The leader of one non-$T(v)$ site can go the left, the two others can go
to the right.

Figure 12: Trying to find a leaf order that induces zero crossings of
s-leaders, we store or reject embeddings of $T(v)$ based on other sites in
$H(v,i)$.

There are at most $n-n(v)$ others sites in $H(v)$. If any of them is trapped,
we reject the embedding. Assume otherwise, namely that for the current
embedding, all of them can reach a position outside of $T(v)$. The leader of
$p_{k}$ then partitions these sites into those that can go out to the left and
those that can go out to the right. Hence, among all suitable embeddings of
$T(v)$ these sites can be partitioned in at most $n(v)$ different ways (since
the leader of $p_{k}$ can go to only that many positions); see Fig. 12(c). For
each such partition, we need to store only one embedding. Therefore, before
storing a suitable embedding of $T(v)$, we first check whether we already
store an embedding where $\ell_{k}$ is at the same position.

We can handle each of the $\mathcal{O}(n(v)^{2})$ embeddings of $T(v)$ in
$\mathcal{O}(n^{2})$ time each. With $n$ positions and $\mathcal{O}(n)$
vertices, we get a running time in $\mathcal{O}(n^{6})$.

####  po-Leaders.

As with s-leaders, we want to store at most $\mathcal{O}(n(v))$ embeddings of
$T(v)$ for po-leaders. Let $H^{\prime}(v,i)$ be the rectangle that
horizontally spans from positions $i$ to $i+n(v)-1$ and vertically from
$p_{k}$ to the top of $R$. For the current embedding of $T(v)$ and for any
site $p_{o}\in P\setminus P(v)$ that lies insides $H^{\prime}(v,i)$, we check
whether the horizontal segment of the leader $s_{o}$ of $p_{o}$ can leave
$H^{\prime}(v,i)$ without intersecting a vertical segment of a leader of
$T(v)$. If this is not the case for one leader, then we reject the embedding;
see Fig. 13(a). Otherwise, the leader $s_{k}$ of $p_{k}$ determines for each
$s_{o}$ whether it can leave $H^{\prime}(v,i)$ on the left or on the right
side. Therefore, $s_{k}$ partitions the sites in $P\setminus P(v)$ that lie
insides $H^{\prime}(v,i)$ and we need to store only one suitable embedding for
each partition; see Fig. 13(b). Note that the horizontal segments of the
leader $s$ of any site of $P(v)$ that lies outside of $H^{\prime}(v,i)$ always
spans to at least $H^{\prime}(v,i)$. Therefore whether $s$ intersects with
another leader later on outside of $H^{\prime}(v,i)$ is independent of the
embedding of $T(v)$. The running time for po-leaders is the same as for
s-leaders and thus also in $\mathcal{O}(n^{6})$.

(a) The non-$T(v)$ site $p_{o}$ inside $H^{\prime}(v,i)$ is blocked by
vertical segments of leaders of $T(v)$. (b) The leader of $p_{k}$ partitions
the non-$T(v)$ sites inside $H^{\prime}(v,i)$ into whether their leader leaves
$H^{\prime}(v,i)$ to the left or the right.

Figure 13: Trying to find a leaf order that induces zero crossings of po-
leaders, we store or reject embeddings of $T(v)$ based on other sites in
$H^{\prime}(v,i)$.

###  4.3 Efficiently Solvable Instances

We now make some observations about the structure of geophylogeny drawings.
This leads to an $\mathcal{O}(n\log n)$-time algorithm for crossing
minimization on a particular class of “geometry-free” instances, and forms the
basis for our FPT algorithm and ILP.

Consider a drawing $\Gamma$ of a geophylogeny $G$ with s-leaders and leaf
order $\pi$. Let $B$ be the line segment between leaf position 1 (left) and
leaf position $n$ (right); let the _s -area_ of a site $p_{i}$ be the triangle
spanned by $p_{i}$ and $B$. Note that the leader $s_{i}$ lies within this
triangle in any drawing. Now consider two sites $p_{i}$ and $p_{j}$ that lie
outside each other’s s-area. Independently of the embedding of the tree,
$s_{i}$ always passes $p_{j}$ on the same side: see Fig. 14 where, for
example, $s_{2}$ passes left of $p_{4}$ in any drawing. As a result, if
$p_{i}$ lies left of $p_{j}$, then $s_{i}$ and $s_{j}$ cross if and only if
the leaf $\ell_{i}$ is positioned right of the leaf $\ell_{j}$, i.e.
$\pi(\ell_{i})>\pi(\ell_{j})$. The case where $p_{i}$ is right of $p_{j}$ is
flipped. We call such a pair $\langle p_{i},p_{j}\rangle$ _geometry free_
since purely the _order_ of the corresponding leaves suffices to recognize if
their leaders cross: the precise geometry of the leaf positions is irrelevant.

(a) A geometry-free drawing for s-leaders: no site lies inside the s-area of
another site. (b) A geometry-free instance for po-leaders: no site lies inside
the po-area of another site.

Figure 14: In a geometry-free instance the leaf order $\pi$ fully determines
if any two leaders cross.

Conversely, consider a site $p_{k}$ that lies inside the s-area of $p_{i}$.
Whether the leaders $s_{i}$ and $s_{k}$ cross depends on the placement of the
leaves $\ell_{i}$ and $\ell_{k}$ in a more complicated way than just their
relative order: $s_{i}$ might pass left or right of $p_{k}$ and it is
therefore more complicated to determine whether $s_{i}$ and $s_{k}$ cross. In
this case, we call the pair $\langle p_{i},p_{k}\rangle$ _undecided_. See Fig.
15, where $p_{1}$ is undecided with respect to $p_{2}$.

Figure 15: Drawings of the same geophylogeny with four different leaf orders.
Note that $s_{1}$ and $s_{3}$ cross if and only if $\ell_{3}$ is left of
$\ell_{1}$. On the other hand, whether $s_{1}$ and $s_{2}$ cross or not
depends more specifically on the positions of $\ell_{1}$ and $\ell_{2}$.

Analogously, for po-leaders, let the _po -area_ of $p_{i}$ be the rectangle
that spans horizontally from position $1$ to position $n$ and vertically from
$p_{i}$ to the top of $R$; see Fig. 14(b). A pair $\langle p_{i},p_{j}\rangle$
of sites is _geometry free_ if $p_{i}$ does not lie in the po-area of $p_{j}$
or vice versa. A pair $\langle p_{i},p_{k}\rangle$ of sites is called
_undecided_ , if $p_{k}$ lies in the po-area of $p_{i}$.

We call a geophylogeny _geometry free_ (for s\- or po-leaders) if all pairs of
sites are geometry free. While it seems unlikely that a geophylogeny is
geometry free for po-leaders in practice, it is not entirely implausible for
s-leaders: for example, researchers may take their samples along a coastline,
a river, or a valley, in which case the sites may lie relatively close to a
line. Orienting the map such that this line is horizontal might then result in
a geometry-free instance. Furthermore, unless two sites share an x-coordinate,
increasing the vertical distance between the map and the tree eventually
results in a geometry-free drawing for s-leaders; however, the required
distance might be impractically large.

Next we show that the number of leader crossings in a geometry-free drawing of
geophylogeny can be minimized efficiently using Fernau et al.’s [19] algorithm
for the One-Sided Tanglegram problem.

######  Proposition 4.5.

Given a geometry-free geophylogeny $G$ on $n$ taxa, a drawing $\Gamma$ with
the minimum number of leader crossings can be found in $\mathcal{O}(n\log n)$
time, for both s\- and po-leaders.

######  Proof 4.6.

To use Fernau et al.’s [19] algorithm, we transform $G$ into a so-called _one-
sided tanglegram_ $(T_{\text{fix}},T_{\text{vari}})$ that is equivalent in
terms of crossing to $\Gamma$; see Fig. 16. We take the sites $P$ as the
leaves of the tree $T_{\text{fix}}$ with fixed embedding and embed it such
that the points are ordered from left to right; the topology of
$T_{\text{fix}}$ is arbitrary. As the tree $T_{\text{vari}}$ with variable
embedding, we take the phylogenetic tree $T$.

If $\Gamma$ uses s-leaders, then we assume that the sites of $G$ are indexed
from left to right. If $\Gamma$ uses po-leaders, we define an (index) order on
$P$ as follows. Let $p_{i}$ be a site and $p_{j}$ a site to the right of it;
consider the leader that connects $p_{i}$ to leaf position $1$ and the leader
that connects $p_{j}$ to leaf position $n$. If these leaders cross, we require
that $i$ is after $j$, otherwise it must be before $j$. (It is easily shown
that this defines an order; see also Fig. 14(b).)

Let $\pi^{\prime}$ be a leaf order of $T_{\text{vari}}$. Further let
$s^{\prime}_{i}$ denote the connection of the leaf corresponding to $p_{i}$ in
$T_{\text{fix}}$ and the leaf $\ell_{i}$ in $T_{\text{vari}}$. Note that two
connections $s^{\prime}_{i}$ and $s^{\prime}_{j}$ with $i<j$ cross in the
tanglegram if and only if $\pi^{\prime}(\ell_{i})>\pi^{\prime}(\ell_{j})$.

Figure 16: A geometry-free geophylogeny and a one-sided tanglegram
$(T_{\text{fix}},T_{\text{vari}})$ that have the same combinatorics (in terms
of leader crossings) as the two geometry-free instances in Fig. 14.

Since $G$ is geometry free, the crossings in the tanglegram correspond one-to-
one with those in the geophylogeny drawing with leaf order $\pi^{\prime}$; see
again Figs. 14 and 16. Hence, the number of crossings of
$(T_{\text{fix}},T_{\text{vari}})$ can be minimized in $\mathcal{O}(n\log n)$
time using an algorithm of Fernau et al. [19]. The resulting leaf order for
$T_{\text{vari}}$ then also minimizes the number of leader crossings in
$\Gamma$.

###  4.4 FPT Algorithm

In practice, most geophylogenies are not geometry free, yet some drawings with
s-leaders might have only few sites inside the s-area of other sites.
Capturing this with a parameter, we can develop an FPT algorithm using the
following idea. Suppose we use s-leaders and there is exactly one undecided
pair $\langle p_{i},p_{j}\rangle$, i.e. $p_{j}$ lies inside the s-area of
$p_{i}$; see Fig. 17(a). For a particular leaf order, we say the leader
$s_{i}$ _lies left (right)_ of $p_{j}$ if a horizontal ray that starts at
$p_{j}$ and goes to the left (right) intersects $s_{i}$; conversely, we say
that $p_{j}$ _lies right (left)_ of $s_{i}$.

Suppose now that we restrict $s_{i}$ to lie left of $p_{j}$ (as $s_{2}$ lies
left of $p_{3}$ in Fig. 17(b)). This restricts the possible positions for
$\ell_{i}$ and effectively yields a _restricted_ geometry-free geophylogeny.
The idea for our FPT algorithm is thus to use the algorithm from Proposition
4.5 on restricted geometry-free instances obtained by assuming that $s_{i}$
lies to the left or to the right of $s_{i}$; see again Fig. 17. In particular,
we extend Fernau et al.’s dynamic programming algorithm [19] to handle
_restricted_ one-sided tanglegrams at a cost in runtime.

(a) A non-geometry-free geophylogeny since $p_{3}$ lies in the s-area of
$p_{2}$.

(b) Restricted geometry-free geophylogeny where we require that $p_{3}$ lies
right of $s_{2}$. Thus $\ell_{2}$ cannot be at positions 3 or 4.

(c) Restricted geometry-free geophylogeny where we require that $p_{3}$ lies
left of $s_{2}$. Thus $\ell_{2}$ cannot be at positions 1 or 2.

Figure 17: We transform the non-geometry-free geophylogeny $G$ into restricted
geometry-free geophylogeny by deciding whether $p_{3}$ lies left or right of
$s_{2}$.

######  Lemma 4.7.

The number of connection crossings in a restricted one-sided tanglegram
$\mathcal{T}$ on $n$ leaves can be minimized in $\mathcal{O}(n^{3})$ time.

######  Proof 4.8.

Let $\mathcal{T}=(T_{\text{fix}},T_{\text{vari}})$; we write $T$ for
$T_{\text{vari}}$. Let $x$ and $y$ be the children of a vertex $v$ of $T$.
Fernau et al.’s algorithm would compute the number of crossings
$\text{cr}(x,y)$ and $\text{cr}(y,x)$ between the connections of $T(x)$ and
the connections of $T(y)$ for when $x$ is the left or right child of $v$,
respectively, in $\mathcal{O}(n(x)+n(y))$ time. For an unrestricted one-sided
tanglegram, this can be done independent of the positions of $T(x)$ and
$T(y)$. For $\mathcal{T}$ however this would not take in account the
forbidding positions of leaves. Hence, as in our algorithm from Theorem 3.1,
we add the position of the leftmost leaf of $T(v)$ as additional parameter in
the recursion. This adds a factor of $n$ to the running time and thus,
forgoing Fernau et al.’s data structures, results in a total running time in
$\mathcal{O}(n^{3})$.

Before describing an FPT algorithm based on restricted geometry-free
geophylogenies, let us consider the example from Fig. 15 again. There the
drawing $\Gamma$ has three sites $p_{1}$, $p_{2}$, $p_{3}$ where $p_{2}$ lies
in the s-area of both $p_{1}$ and $p_{3}$. We can get four restricted
geometry-free geophylogenies by requesting that $p_{2}$ lies to the left or to
the right of $s_{1}$ and of $s_{3}$. Here one of the instances, $G^{\prime}$,
stands out, namely where $p_{2}$ lies to the left of $s_{1}$ and to the right
of $s_{3}$; see Fig. 18(a). In the restricted one-sided tanglegram
$\mathcal{T}^{\prime}$ corresponding to $G^{\prime}$, we would want $p_{2}$
left of $p_{1}$ and right of $p_{3}$. This stands in conflict with $p_{1}$
being left of $p_{3}$ based on their indices. We thus say $p_{1}$, $p_{2}$,
and $p_{3}$ form a _conflicting triple_ $\langle p_{1},p_{2},p_{3}\rangle$,
which we resolve as follows. Note that $s_{1}$ and $s_{3}$ cross for any valid
leaf order for $G^{\prime}$. We thus use the order $p_{3}$, $p_{2}$, $p_{1}$
for $\mathcal{T}^{\prime}$ (see Fig. 18(b)) and, since $\mathcal{T}^{\prime}$
does not contain the crossing of $s^{\prime}_{1}$ and $s^{\prime}_{3}$, we add
one extra crossing to the computed solution. A conflicting triple for drawings
with po-leaders is defined analogously.

(a) Restricted geometry-free geophylogeny with conflicting triple $\langle
p_{1},p_{2},p_{3}\rangle$. Note that $s_{1}$ and $s_{3}$ cross for any valid
leaf order.

(b) Restricted one-sided tanglegram $\mathcal{T}^{\prime}$ with order $p_{3}$,
$p_{2}$, $p_{1}$. Note that $s^{\prime}_{1}$ and $s^{\prime}_{3}$ do not cross
for any valid leaf order.

Figure 18: A conflicting triple in a restricted geometry-free instance
requires a different order in the corresponding restricted one-sided
tanglegram and storing the “lost” crossing.

######  Theorem 4.9.

Given a _geometry-free_ geophylogeny $G$ on $n$ taxa and with $k$ undecided
pairs of sites, a drawing $\Gamma$ of $G$ with minimum number of crossings can
be computed in $\mathcal{O}(2^{k}\cdot(k^{2}+n^{3}))$ time, for both s\- and
po-leaders.

######  Proof 4.10.

Our FPT algorithm converts $G$ into up to $2^{k}$ restricted geometry-free
instances, solves the corresponding restricted one-sided tanglegrams with
Lemma 4.7, and then picks the leaf order that results in the least leader
crossings for $\Gamma$. Therefore, for each undecided pair $\langle
p_{i},p_{j}\rangle$, the algorithm tries routing $s_{i}$ either to the left of
or to the right of $p_{j}$. Since there are $k$ such pairs, there are $2^{k}$
different combinations. However, for some combinations a drawing might be over
restricted and no solution exists.

To keep track of all possible combinations, we go through all words over the
alphabet $\\{0,1\\}$ of length $k$. Suppose that we consider one such word
$\omega$. Let the $k$ pairs be in some arbitrary order. For the $m$-th pair
$\langle p_{i},p_{j}\rangle$, we set $s_{i}$ to be left of $p_{j}$ if
$\omega[m]=0$ and to be right of $p_{j}$ if $\omega[m]=1$. Below we show how
to construct the restricted geometry-free instances $G_{\omega}$ and the
corresponding restricted one-sided tanglegram $\mathcal{T}_{\omega}$ in
$\mathcal{O}(k^{2}+n^{2})$ time. Since the number of crossings in the
restricted geometry-free drawing can then be minimized in $\mathcal{O}(n^{3})$
time with Lemma 4.7, the claim on the running time follows.

In order to construct $\Gamma_{\omega}$ efficiently, we keep track of the
positions where a leaf $\ell_{i}$, for $i\in\\{1,\ldots,n\\}$, can be placed
with an interval $[a_{i},b_{i}]$; at the start we have $a_{i}=0$ and
$b_{i}=n$. Suppose that when going through the $k$ pairs and $\omega$, we get
that $s_{i}$ becomes restricted by, say, having to be left of a site $p_{j}$.
Then we compute the rightmost position where $\ell_{i}$ could be placed and
update $b_{i}$ accordingly. This can both be done in constant time. If at any
moment $a_{i}>b_{i}$, then the drawing for $\omega$ is over restricted and
there is no viable leaf order. We then continue with the next word. Otherwise,
after all $k$ pairs, we have restricted $G$ to $G_{\omega}$ in
$\mathcal{O}(k)$ time.

Next, we explain how to find an order of $P$ for $\mathcal{T}_{\omega}$ that
corresponds to $G_{\omega}$. In particular, we have to show that resolving all
conflicting triples as described above in fact yields an order of $P$. To this
end, let $K$ be the complete graph with vertex set $P$. (We assume again the
same order on the sites as in Proposition 4.5.) For any two sites
$p_{i},p_{j}\in P$ with $i<j$, we orient $\\{p_{i},p_{j}\\}$ as
$(p_{j},p_{i})$ if $\langle p_{i},p_{j}\rangle$ is an undecided pair and
$s_{i}$ is right of $p_{j}$ in $G_{\omega}$; otherwise we orient it as
$(p_{i},p_{j})$. We then check whether any pair of undecided pairs forms a
conflicting triple. For any conflicting triple $\langle
p_{i},p_{j},p_{l}\rangle$ that we find, we reorient the edge between $p_{i}$
and $p_{l}$ to $(p_{l},p_{i})$. We claim that $K$ is acyclic (and prove it
below). Therefore we can use a topological order of $K$ as order for
$\mathcal{T}_{\omega}$. For $i\in\\{1,\ldots,n\\}$, we set the dynamic
programming values for leaf $\ell_{i}$ at all positions in
$\mathcal{T}_{\omega}$ outside of $[a_{i},b_{i}]$ to infinity. We can find all
conflicting triples in $\mathcal{O}(k^{2})$ time, construct and orient $K_{n}$
in $\mathcal{O}(n^{2})$ time, and initialize $\mathcal{T}$ in
$\mathcal{O}(n^{2})$ time.

Lastly, we show that $K$ is indeed acyclic after resolving all conflicting
triples. Suppose to the contrary that there is a directed cycle $C^{\prime}$
in $K$. Since the underlying graph of $K$ is the complete graph, there is then
also a directed triangle $C$ in $K$. To arrive at a contradiction, we show
that $C$ cannot have 0, 1, 2, or 3 reoriented edges. Let $C$ be on $p_{i}$,
$p_{j}$, $p_{l}$ with edges $(p_{i},p_{j})$, $(p_{j},p_{l})$, and
$(p_{l},p_{i})$.

$C$ contains 0 reoriented edges: Since $p_{i}$, $p_{j}$, and $p_{l}$ do not
form a conflicting triple, an easy geometric case distinction shows that this
is not geometrically realizable. For example, if, say, $p_{i}$ is lower than
$p_{j}$ and $p_{j}$ is lower than $p_{l}$, then $p_{j}$ is right of $s_{i}$
and $p_{l}$ is right of $s_{j}$. However, then $p_{l}$ cannot be left of
$s_{i}$ and $p_{i}$ cannot be right of $s_{l}$; see Fig. 19(a).

(a) If $C$ contains no reoriented edge and $p_{i}$, $p_{j}$, $p_{l}$ are not a
conflicting triple, then there is no geometric realization respecting $C$;
here $(p_{l},p_{i})$ is not realized.

(b) If $C$ contains one reoriented edge $(p_{i},p_{j})$, there is no placement
of $p_{l}$ respecting $C$ where $p_{l}$ is not part of a conflicting triple
with $p_{i}$ (as here) or $p_{j}$.

(c) If $C$ contains two reoriented edges $(p_{i},p_{j})$ and $(p_{j},p_{l})$,
we get that $p_{k}$ must lie right of $s_{i}$.

Figure 19: Cases for the proof of Theorem 4.9 where the directed triangle $C$
with edges $(p_{i},p_{j})$, $(p_{j},p_{l})$, and $(p_{l},p_{i})$ is supposed
to contains no, one, or two reoriented edges. Colored cones represent a
hypothetical possible range for the leader of the corresponding site.

$C$ contains 1 reoriented edges: Suppose that $(p_{i},p_{j})$ has been
reoriented as part of a conflicting triple with $p_{m}$. Note that $p_{m}$
also lies in the s-area (po-area) of $p_{l}$, since either $p_{i}$ or $p_{j}$
lies in the s-area (po-area) of $p_{l}$ or $p_{l}$ lies right of $p_{j}$, left
of $p_{i}$, and below where $s_{i}$ and $s_{j}$ definitely cross. However,
then based on the orientation of $(p_{j},p_{l})$, and $(p_{l},p_{i})$, we get
that $p_{l}$ must for a conflict triple with $p_{m}$ and either $p_{i}$ or
$p_{j}$; see Fig. 19(b). This stands in contradiction to $C$ containing only
one reoriented edge.

$C$ contains 2 reoriented edges: Suppose that $(p_{i},p_{j})$ and
$(p_{j},p_{l})$ have been reoriented. We then know that $s_{i}$ and $s_{j}$ as
well as $s_{j}$ and $s_{l}$ definitely cross. Therefore, $p_{i}$ lies right of
$s_{j}$ (or the line through $s_{j}$) and that $p_{j}$ lies left of $s_{i}$
(or the line through $s_{i}$). Analogously, $p_{j}$ lies right of $s_{j}$ (or
the line through $s_{l}$), and that $p_{l}$ lies left of $s_{j}$ (or the line
through $s_{j}$). Since $(p_{l},p_{i})$ has not been reoriented, we know that
$s_{i}$ and $s_{l}$ do not necessarily need to cross. For $s_{l}$ to cross
$s_{j}$ but not $s_{i}$, we get that $p_{l}$ can only lie right of $s_{i}$;
see Fig. 19(c). This stands in contradiction to the orientation of
$(p_{l},p_{i})$.

$C$ contains 3 reoriented edges: Since all three edges of $C$ have been
reoriented, this is geometrically equivalent to the first case and thus not
realizable.

This concludes the proof that there is no directed triangle in $K$ and hence
$K$ is acyclic. Our FPT algorithm can thus process each of the $2^{k}$ words
in $\mathcal{O}(k^{2}+n^{2})$ time.

Note that a single site can lie in the s-area of every other site, for
example, this is likely for a site that lies very close to the top of the map.
Furthermore, there can be $\mathcal{O}(n^{2})$ undecided pairs. In these
cases, the running time of the FPT algorithm becomes $\mathcal{O}(2^{n}n^{2})$
or even $\mathcal{O}(2^{(}n^{2})n^{4})$. However, a brute-force algorithm that
tries all $2^{(}n-1)$ embeddings of $T$ and computes for each the number of
leader crossings in $\mathcal{O}(n^{2})$ time, only has a running time in
$\mathcal{O}(2^{n}n^{2})$.

###  4.5 Integer Linear Programming

As we have seen above, the problem of minimizing the number of leader
crossings in drawings of geophylogenies is NP-hard and the preceding
algorithms can be expected to be impractical on realistic instances; we have
not implemented them. We now provide a practical method to exactly solve
instances of moderate size using integer linear programming (ILP).

For the following ILP, we consider an arbitrary embedding of the tree as
_neutral_ and describe all embeddings in terms of which internal vertices of
$T$ are rotated with respect to this neutral embedding, i.e. for which
internal vertices to swap the left-to-right order of their two children. For
two sites $p_{i}$ and $p_{j}$, we use $p_{i}\prec p_{j}$ to denote that
$\ell_{i}$ is left of $\ell_{j}$ in the neutral embedding. Let $U$ be the set
of undecided pairs, that is, all ordered pairs $(p,q)$ where $q$ lies inside
the s-area of $p$; note that these are ordered pairs.

#### Variables and Objective Function.

The program has three groups of binary variables that describe the embedding
and crossings.

$\rho_{i}\in\\{0,1\\}\ \forall i\in I(T)$.

Rotate internal vertex $i$ if $\rho_{i}=1$ and keep its neutral embedding if
$\rho_{i}=0$. Note that rotating the lowest common ancestor of $\ell_{i}$ and
$\ell_{j}$ is the only way to flip their order, so for convenience we write
$\rho_{ij}$ to mean $\rho_{\text{lca}(i,j)}$. Note, however, that an internal
vertex can be the lowest common ancestor of multiple pairs of leaves.

$d_{pq}\in\\{0,1\\}\ \forall(p,q)\in U$.

For each undecided pair $(p,q)$: the leader for $p$ leader should pass to the
left of site $q$ if $d_{pq}=0$ and to the right if $d_{pq}=1$. This is well-
defined since the pair is undecided.

$\chi_{pq}\in\\{0,1\\}\ \forall p,q\in P,\,p<q$.

For each pair of distinct sites: the leaders of $p$ and $q$ are allowed to
cross if $\chi_{pq}=1$ and are not allowed to cross if $\chi_{pq}=0$.

There is no requirement that non-crossing pairs have $\chi_{pq}=0$, but that
will be the case in an optimal solution: to minimise the number of crossings,
we minimize the sum over all $\chi_{pq}$.

#### Constraints.

We handle geometry-free pairs and undecided pairs separately.

Consider a geometry-free pair of sites: if the leaders cross in the neutral
embedding, we must either allow this, or rotate the lowest common ancestor.
Conversely, if they do not cross neutrally, yet we rotate the lowest common
ancestor, then we must allow their leaders to cross. Call these sets of pairs
$F_{\text{rotate}}$ and $F_{\text{keep}}$ respectively, for how to prevent the
crossing.

$\chi_{ij}+\rho_{ij}\geq 1\quad\quad\forall(i,j)\in F_{\text{rotate}}$ (2)
$\chi_{ij}-\rho_{ij}\geq 0\quad\quad\forall(i,j)\in F_{\text{keep}}$ (3)

For undecided pairs $(p,q)$, a three-way case distinction on $[p\prec q]$,
$\rho_{pq}$, and $d_{pq}$ reveals the following geometry:

  * •

pairs with $p\prec q$ have crossing leaders if and only if
$\rho_{pq}+d_{pq}=1$;

  * •

pairs with $p\succ q$ have crossing leaders if and only if
$\rho_{pq}+d_{pq}\neq 1$.

Recall that we do not force $\chi$ to be zero if there is no intersection,
only that it is $1$ if there is an intersection. We implement these conditions
in the ILP as follows. Let $U_{\text{left}}\subseteq U$ be the undecided pairs
with $p\prec q$.

$\rho_{pq}-d_{pq}\leq\chi_{pq}\quad\quad\forall(p,q)\in U_{\text{left}}$ (4)
$d_{pq}-\rho_{pq}\leq\chi_{pq}\quad\quad\forall(p,q)\in U_{\text{left}}$ (5)

Conversely, let $U_{\text{right}}\subseteq U$ be the undecided pairs with
$p\succ q$.

$\rho_{pq}+d_{pq}-1\leq\chi_{pq}\quad\quad\forall(p,q)\in U_{\text{right}}$
(6) $1-\rho_{pq}-d_{pq}\leq\chi_{pq}\quad\quad\forall(p,q)\in
U_{\text{right}}$ (7)

Finally, we must ensure that each leader $s_{i}$ respects the $d$ variables:
the line segment from $p_{i}$ to $\ell_{i}$ must pass by each other site in
the s-area on the correct side. By their definition, this does not affect
geometry-free pairs, but it remains to constrain the leaf placement for
undecided pairs.

Observe that the $\rho$ variables together fix the leaf order, since they fix
the embedding of $T$. Let $L_{i}(\rho)$ be the function that gives the
x-coordinate of $\ell_{i}$ given the $\rho$ variables. Note that $L_{i}$ is
linear in each of the $\rho$ variables: rotating an ancestor of $\ell_{i}$
shifts its location leaf by a particular constant, and rotating a non-ancestor
does not affect it.

(a) s-leaders

(b) po-leaders

Figure 20: Defining $\operatorname{\text{x}}^{*}(i,j)$ by extending a leader
from $s_{i}$ through $s_{j}$ This partitions the leaf positions into those
where the leader goes left of $s_{j}$ and those where it goes right.

For an undecided pair $(p_{i},p_{j})$, consider a leader starting at $s_{i}$
and extending up through $s_{j}$: for s-leaders this is the ray from $s_{i}$
through $s_{j}$, for po-leaders this is the vertical line through $s_{j}$. Let
$\operatorname{\text{x}}^{*}(i,j)$ be the x-coordinate of where this extended
leader intersects the top of the map and note that this is a constant; see
Fig. 20(b). If $d_{ij}=0$, then $\ell_{i}$ must be to the left of this
intersection; if $d_{ij}=1$, it must be to the right. We model this in the ILP
with two constraints and the _big-M method_ , where it suffices to set $M=n$.

$L_{i}(\rho)-d_{ij}M\leq\operatorname{\text{x}}^{*}(i,j)\quad\quad\forall(p_{i},p_{j})\in
U$ (8)
$L_{i}(\rho)+(1-d_{ij})M\geq\operatorname{\text{x}}^{*}(i,j)\quad\quad\forall(p_{i},p_{j})\in
U$ (9)

This completes the ILP.

The number of variables and constraints are both quadratic in $n$. Just
counting the $\chi$ variables already gives this number, but we note that in
particular the number of undecided pairs leads to additional variables (and
seemingly more complicated constraints).

###  4.6 Heuristics

Since the ILP from the previous section can be slow in the worst case and
requires advanced solver software, we now suggest a number of heuristics.

#### Bottom-Up.

First, we use a dynamic program similar to the one in Section 3 and commit to
an embedding for each subtree while going up the tree. At this point we note
that counting the number of crossings is not a leaf additive objective
function in the sense of Section 3. However, Eq. 1 does enable us to introduce
an additional cost based on where an entire subtree is placed and where its
sibling subtree is placed – just not minimized over the embedding of these
subtrees. More precisely, for an inner vertex $v$ of $T$ with children $x$ and
$y$, let $C(x,y,i)$ be the number of crossings between $T(x)$ and $T(y)$ when
placed starting at position $i$ and $i+n(x)$ respectively; this can be
computed in $\mathcal{O}(n(v)^{2})$ time. Note that this ignores any crossings
with leaders from other parts of the tree. With base case $H(\ell,i)=0$ for
every leaf $\ell$, we use

$H(v,i)=\min\\{\quad H(x,i)+H(y,i+n(x))+C(x,y,i),\quad
H(y,i)+H(x,i+n(y))+C(y,x,i)\quad\\}$

to pick a rotation of $T(v)$. Since $H$ can be evaluated in
$\mathcal{O}(n^{2})$ time, the heuristic runs in $\mathcal{O}(n^{4})$ time
total. The example in Fig. 21 demonstrates that this does not minimize the
total number of crossings.

(a) When $T(x)$ and $T(y)$ each have zero crossings, …

(b) …then $T(v)$ has two crossings.

(c) The optimal leaf order for $T(v)$ has one crossing in $T(x)$.

Figure 21: The bottom-up heuristic is not always optimal: combining the
locally best leaf orders for $T(x)$ and $T(y)$ might not result in the minimum
number of leader crossings for $T(v)$.

#### Top-Down.

The second heuristic traverses $T$ from top to bottom (i.e. in pre-order) and
chooses a rotation for each inner vertex $v$ based on how many leaders would
cross the vertical line between the two subtrees of $v$; see Fig. 22. More
precisely, suppose that $T(v)$ has its leftmost leaf at position $i$ based on
the rotations of the vertices above $v$. For $x$ and $y$ the children of $v$,
consider the rotation of $v$ where $T(x)$ is placed starting at position $i$
and $T(y)$ is placed starting at position $i+n(x)$. Let $s$ be the
x-coordinate in the middle between the last leaf of $T(x)$ and the first leaf
$T(y)$. We compute the number of leaders of $T(v)$ that cross the vertical
line at $s$ and for the reserve rotation of $v$; the smaller result is chosen
and the rotation fixed. This procedure considers each site at most
$\mathcal{O}(n)$ times and thus runs in $\mathcal{O}(n^{2})$ time.

(a) $T(x)$ and $T(y)$ have one site each on the other side of the vertical
line through $s$.

(b) $T(x)$ has one and $T(y)$ has two sites on the other side of the vertical
line through $s$.

Figure 22: The top-down heuristic tries both rotations of $v$ and here would
pick (a).

#### Leaf-Additive Dynamic Programming.

Thirdly, we could optimize any of the quality measures for interior labeling
(Section 3). These measures produce generally sensible leaf orders in
quadratic time and we may expect the number of leader crossings to be low.

#### Greedy (Hill Climbing).

Finally, we consider a hill climbing algorithm that, starting from some leaf
order, greedily performs rotations that improve the number of crossings. This
could start from a random leaf order, a hand-made one, or from any of the
other heuristics. Evaluating a rotation can be done in $\mathcal{O}(n^{2})$
time and thus one round through all vertices runs in $\mathcal{O}(n^{3})$
time.

##  5 Experimental Evaluation

This section is based on our implementation of the ILP and the heuristics. The
code is available online at github.com/joklawitter/geophylo, and data from the
corresponding authors upon request.

###  5.1 Test Data

We use three procedures to generate random instances. For each type and with
10 to 100 taxa (in increments of 5), we generated 10 instances; we call these
the _synthetic instances_. We stop at $100$ since geophylogeny drawings with
more taxa are rarely well-readable. Example instances are shown in Fig. 23.

Uniform

Place $n$ sites on the map uniformly at random. Generate the phylogenetic tree
by repeating the following merging procedure. Pick an unmerged site or a
merged subtree uniformly at random, then pick a second with probability
distributed by inverse distance to the first, and merge them; as position of a
subtree, we take the median coordinate on both axes.

Coastline

Initially place all sites equidistantly on a horizontal line, then slightly
perturb the x-coordinates. Next, starting at the central site and going
outwards in both directions, change the y-coordinate of each site randomly (up
to $1.5$ times the horizontal distance) from the y-coordinate of the previous
site. Construct the tree as before.

Clustered

These instances group multiple taxa into clusters. First a uniformly random
number of sites between three and ten is allocated for a cluster and its
center is placed at a uniformly random point on the map. Then for each
cluster, we place sites randomly in a disk around the center with size
proportional to the cluster size. Construct $T$ as before, but first for each
cluster separately and only then for the whole instance.

In addition, we consider three real world instances derived from published
drawings. Fish is a 14-taxon geophylogeny by Williams and Johnson [46].
Lizards is 20-taxon geophylogeny by Jauss et al. [26], where the sites are
mostly horizontally dispersed (see Fig. 2(b)). Frogs is a 64-taxon
geophylogeny by Ellepola et al. [18], where the sites are rather chaotically
dispersed on the map; the published drawing of Frogs uses s-leaders and has
over 680 crossings.

(a) uniform

(b) coastline

(c) cluster

Figure 23: Examples of generated instances with 20 taxa, here shown with
s-leaders. The leaf order was computed with the Greedy hill climber.

###  5.2 Experimental Results

We now describe the main findings from our computational experiments.

#### The ILP is fairly quick for s-leaders.

Our implementation uses Python to generate the ILP instance and Gurobi 10 to
solve it; we ran the experiments on a 10-core Apple M1 Max processor. The
Python code takes negligible time; practically all time is spent in the ILP
solver. As expected, we observe that the running time is exponential in $n$,
but only moderately so (Fig. 24). Instances with up to about 50 taxa can
usually be solved optimally within a second, but for Clustered and Uniform
instances the ILP starts to get slow at about 100 taxa. We note that
geophylogenies with over $100$ taxa should probably not be drawn with external
labeling: for example, the Frogs instance can be drawn optimally by the ILP in
about $0.5\text{\,}\mathrm{s}$, but even though this improves the number of
crossings from the published 680 to the optimal 609, the drawing is so messy
as to be unreadable (Fig. 26(b)). We further observe that Coastline instances
are solved trivially fast, since with fewer undecided pairs the ILP is smaller
and presumably easier to solve.

#### The ILP is noticeably slower for po-leaders.

Instances with up to $25$ taxa are still drawn comfortably within a second,
but at $50$ taxa the typical runtime is over a minute. We conjecture this is
due to the increased number of undecided pairs when working with po-leaders.

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$n$Runtime
[ s ]UniformCoastlineClustered (a) Runtime

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$0$$200$$400$$600$$800$$1{,}000$$1{,}200$$1{,}400$$1{,}600$$1{,}800$$n$OPTUniformCoastlineClustered
(b) Number of crossings.

Figure 24:  Computing optimal s-leader drawings using the ILP.

#### The synthetic instances have a superlinear number of crossings.

The Clustered instances can be drawn with significantly fewer crossings than
Uniform: this matches our expectation, as by construction there is more
correlation between the phylogenetic tree and the geography of the sites. More
surprisingly we find that the Coastline instances require many crossings. We
may have made these geophylogenies too noisy, but this observation does warn
of the generally quadratic growth in number of crossings, which makes external
labeling unsuitable for large geophylogenies unless the geographic correlation
is exceptionally good.

#### The heuristics run instantly and Greedy is often optimal.

The heuristics are implemented in single-threaded Java code. Bottom-Up, Top-
Down and Leaf-Additive all run instantly, and even the Greedy hill climber
runs in a fraction of a second. Of the first three heuristics, Bottom-Up
consistently achieves the best results for both s\- and po-leaders. Comparing
the best solution by these heuristics with the optimal drawing (Fig. 25), we
observe that the number crossings in excess of the optimum increases with the
number of taxa, in particular for Uniform and Clustered instances; Coastline
instances are always drawn close to optimally by at least one heuristic. The
Greedy hill climber almost always improves this to an optimal solution.

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$0$$2$$4$$6$$8$$10$$12$$n$Average
excess crossingsUniformCoastlineClustered (a) Best heuristic without Greedy.

$10$$20$$30$$40$$50$$60$$70$$80$$90$$100$$0$$0.1$$0.2$$0.3$$0.4$$0.5$$0.6$$0.7$$0.8$$n$Average
excess crossingsUniformCoastlineClustered (b) Best after Greedy
postprocessing.

Figure 25: Average number of s-leader crossings made by the best heuristic
minus the number of s-leader crossings in the optimal drawing, averaged over
10 random instances per value of $n$.

#### For the number of crossings, po-leaders are promising.

Our heuristics require on average only about 73% as many crossings when using
po-leaders compared to s-leaders (55% for Coastline instances); the Lizard
example in Fig. 2(b) requires 11 s-leader crossings but only 2 po-leader
crossings. We therefore propose that po-leaders deserve more attention from
the phylogenetic community.

#### Algorithmic recommendations.

Our results show that the ILP is a good choice for geophylogeny drawings with
external labeling. If no solver software is at hand or it is technically
challenging to set up (for example when making an app that runs locally in a
user’s web browser), then the heuristics offer an effective and efficient
alternative, especially Bottom-Up and Greedy.

For the Fish instance, for example, we found that the drawing with s-leaders
and 17 crossings in Fig. 26(a) is a good alternative to the internal labeling
used in the published drawing [46]. However, for instances without a clear
structure or with many crossings, it might be better to use internal labeling.
Alternatively, the tree could be split like Tobler et al. [43], such that
different subtrees are each shown with the map in separate drawings.

(a) Drawing of Fish with 17 crossings.

(b) Drawing of Frogs with 609 crossings.

Figure 26: Crossing-optimal drawings of Fish and Frogs with s-leaders.

##  6 Discussion and Open Problems

In this paper, we have shown that drawings of geophylogenies can be approached
theoretically and practically as a problem of algorithmic map labeling. We
formally defined a drawing style for geophylogenies that uses either internal
labeling with text or colors, or that uses external labeling with s/po-
leaders. This allowed us to define optimization problems that can be tackled
algorithmically. For drawings with internal labeling, we introduced a class of
quality measures that can be optimized efficiently and even interactively
provided with user hints. In practice, designers can thus try different
quality measures, pick their favorite, and make further adjustments easily
even for large instances. For external labeling, minimizing the number of
leader crossings is NP-hard in general. Crossing free-instances on the hand
can be found in polynomial time, yet our algorithm still runs only in
$\mathcal{O}(n^{6})$ time. Furthermore, for drawings with s-leaders, we showed
that if the sites lie relatively close to a horizontal line then in the best
scenario an $\mathcal{O}(n\log n)$-time algorithm and otherwise an FPT
algorithm can be used. While we found similar results for drawings with po-
leaders, it seems unlikely that geophylogenies arising in practice have the
required properties. Hence, we provide multiple algorithmic approaches to
solve this problem and demonstrated experimentally that they perform well in
practice.

Even though we have provided a solid base of results, we feel the algorithmic
study of geophylogeny drawings holds further promise by varying, for example,
the type of leader used, the objective function, the composition of the
drawing, or the nature of the phylogeny and the map. Several of these
directions show parallels to the variations found in boundary labeling
problems. We finish this paper with several suggestions for future work.

One might consider do\- and pd-leaders, which use a diagonal segment and can
be aesthetically pleasing; see Fig. 27. We expect that some of our results
(such as the NP-hardness of crossing minimization and the effectiveness of the
heuristics) should hold for these leader types. The boundary labeling
literature [7] studies even further types, such as opo and Bézier, and these
might be more challenging to adapt.

Figure 27: Drawing of a geophylogeny with do\- and pd-leaders.

For external labeling we have only considered the total number of crossings.
If different colors are used for the leaders of different clades or if the
drawing can be explored with an interactive tool, one might want to minimize
the number of crossings within each clade (or a particular clade).
Furthermore, one might optimize crossing angles or insist on a minimum
distance between leaders and unrelated sites. While we provided heuristics to
minimize leader crossings, the development of approximation algorithms, which
exist for other labeling problems [33, 5], could be of interest.

Our model of a geophylogeny drawing can be expanded as well. One might allow
the orientation of the map to be freely rotated, the extent of the map to be
changed, or the leaves to be placed non-equidistantly. Optimizing over these
additional freedoms poses new algorithmic challenges. Straying further from
our model, some drawings in the literature have a circular tree around the map
[37, 28]; see Fig. 28. This is similar to contour labeling in the context of
map labeling [35]. Also recall that Fig. 1 has area features. Our quality
measures for internal labeling are easily adapted to handle this, but (as is
the case with general boundary labeling [6]) area features provide additional
algorithmic challenges for external labeling. The literature contains many
drawings where multiple taxa correspond to the same feature on the map [13]
(see also again Fig. 28) and where we might want to look to many-to-one
boundary labeling [33, 4]. Furthermore, one can consider non-binary
phylogenetic trees and phylogenetic networks.

Figure 28: A drawing of a geophylogeny by Pan et al. [37], where the tree is
drawn circularly around the map and instead of a site per taxa only regions
for clades are given.

Lastly, we note that side-by-side drawings can also be used for a phylogenetic
tree together with a diagram other than a map: Chen et al. [15] combine it
with a scatter plot; Gehring et al. [21] even combine three items
(phylogenetic tree, haplotype network, and map).

## References

  * [1] Wikipedia: List of phylogenetic tree visualization software.  https://en.wikipedia.org/wiki/List_of_phylogenetic_tree_visualization_software.  Accessed: 16.11.2022.
  * [2] Christian Bachmaier, Ulrik Brandes, and Barbara Schlieper.  Drawing phylogenetic trees.  In Xiaotie Deng and Ding-Zhu Du, editors, International Symposium Algorithms and Computation (ISAAC), volume 3827 of LNCS, pages 1110–1121, 2005.  doi:10.1007/11602613_110.
  * [3] Lukas Barth, Andreas Gemsa, Benjamin Niedermann, and Martin Nöllenburg.  On the readability of leaders in boundary labeling.  Information Visualization, 18(1), 2019.  doi:10.1177/1473871618799500.
  * [4] Michael A. Bekos, Sabine Cornelsen, Martin Fink, Seok-Hee Hong, Michael Kaufmann, Martin Nöllenburg, Ignaz Rutter, and Antonios Symvonis.  Many-to-one boundary labeling with backbones.  Journal of Graph Algorithms and Applications, 19(3):779–816, 2015\.  doi:10.7155/jgaa.00379.
  * [5] Michael A. Bekos, Michael Kaufmann, Dimitrios Papadopoulos, and Antonios Symvonis.  Combining traditional map labeling with boundary labeling.  In Ivana Cerná, Tibor Gyimóthy, Juraj Hromkovic, Keith G. Jeffery, Rastislav Královic, Marko Vukolic, and Stefan Wolf, editors, SOFSEM 2011, volume 6543 of LNCS, pages 111–122. Springer, 2011\.  doi:10.1007/978-3-642-18381-2_9.
  * [6] Michael A. Bekos, Michael Kaufmann, Katerina Potika, and Antonios Symvonis.  Area-feature boundary labeling.  The Computer Journal, 53(6):827–841, 2010.  doi:10.1093/comjnl/bxp087.
  * [7] Michael A. Bekos, Benjamin Niedermann, and Martin Nöllenburg.  External labeling techniques: A taxonomy and survey.  Computer Graphics Forum, 38(3):833–860, 2019.  doi:10.1111/cgf.13729.
  * [8] R Alexander Bentley, William R Moritz, Damian J Ruck, and Michael J O’Brien.  Evolution of initiation rites during the austronesian dispersal.  Science Progress, 104(3):00368504211031364, 2021.  doi:10.1177/00368504211031364.
  * [9] Juan José Besa, Michael T. Goodrich, Timothy Johnson, and Martha C. Osegueda.  Minimum-width drawings of phylogenetic trees.  In Yingshu Li, Mihaela Cardei, and Yan Huang, editors, Combinatorial Optimization and Applications (COCOA), volume 11949 of LNCS, pages 39–55, 2019.  doi:10.1007/978-3-030-36412-0_4.
  * [10] Remco R. Bouckaert.  DensiTree: making sense of sets of phylogenetic trees.  Bioinformatics, 26(10):1372–1373, 2010.  doi:10.1093/bioinformatics/btq110.
  * [11] Kevin Buchin, Maike Buchin, Jaroslaw Byrka, Martin Nöllenburg, Yoshio Okamoto, Rodrigo I. Silveira, and Alexander Wolff.  Drawing (complete) binary tanglegrams - hardness, approximation, fixed-parameter tractability.  Algorithmica, 62(1-2):309–332, 2012.  doi:10.1007/s00453-010-9456-3.
  * [12] Tiziana Calamoneri, Valentino Di Donato, Diego Mariottini, and Maurizio Patrignani.  Visualizing co-phylogenetic reconciliations.  Theoretical Computer Science, 815:228–245, 2020.  doi:10.1016/j.tcs.2019.12.024.
  * [13] Tyler K Chafin, Marlis R Douglas, Whitney JB Anthonysamy, Brian K Sullivan, James M Walker, James E Cordes, and Michael E Douglas.  Taxonomic hypotheses and the biogeography of speciation in the tiger whiptail complex.  Frontiers, 13(2), 2021.  doi:10.21425/F5FBG49120.
  * [14] Zachary Charlop-Powers and Sean F. Brady.  phylogeo: an R package for geographic analysis and visualization of microbiome data.  Bioinformatics, 31(17):2909–2911, 2015.  doi:10.1093/bioinformatics/btv269.
  * [15] Yi Chen, Lei Zhao, Huajing Teng, Chengmin Shi, Quansheng Liu, Jianxu Zhang, and Yaohua Zhang.  Population genomics reveal rapid genetic differentiation in a recently invasive population of rattus norvegicus.  Frontiers in Zoology, 18(1):6, 2021.  doi:10.1186/s12983-021-00387-z.
  * [16] Andreas W. M. Dress and Daniel H. Huson.  Constructing splits graphs.  Transactions on Computational Biology and Bioinformatics, 1(3):109–115, 2004.  doi:10.1145/1041503.1041506.
  * [17] Tim Dwyer and Falk Schreiber.  Optimal leaf ordering for two and a half dimensional phylogenetic tree visualisation.  In Neville Churcher and Clare Churcher, editors, Australasian Symposium on Information Visualisation, volume 35 of CRPIT, pages 109––115. Australian Computer Society, 2004.  doi:10.5555/1082101.1082114.
  * [18] Gajaba Ellepola, Jayampathi Herath, Kelum Manamendra-Arachchi, Nayana Wijayathilaka, Gayani Senevirathne, Rohan Pethiyagoda, and Madhava Meegaskumbura.  Molecular species delimitation of shrub frogs of the genus pseudophilautus (anura, rhacophoridae).  PLOS ONE, 16(10):1–17, 2021.  doi:10.1371/journal.pone.0258594.
  * [19] Henning Fernau, Michael Kaufmann, and Mathias Poths.  Comparing trees via crossing minimization.  Journal of Computer and System Sciences, 76(7):593–608, 2010.  doi:10.1016/j.jcss.2009.10.014.
  * [20] Michael R Garey and David S Johnson.  Computers and intractability, volume 174.  freeman San Francisco, 1979.
  * [21] Philip-Sebastian Gehring, Maciej Pabijan, Jasmin E. Randrianirina, Frank Glaw, and Miguel Vences.  The influence of riverine barriers on phylogeographic patterns of malagasy reed frogs (heterixalus).  Molecular Phylogenetics and Evolution, 64(3):618–632, 2012.  doi:10.1016/j.ympev.2012.05.018.
  * [22] Steffen Hadlak, Heidrun Schumann, and Hans-Jörg Schulz.  A survey of multi-faceted graph visualization.  In Rita Borgo, Fabio Ganovelli, and Ivan Viola, editors, Eurographics Conference on Visualization(EuroVis’15), pages 1–20. Eurographics Association, 2015.  doi:10.2312/eurovisstar.20151109.
  * [23] Daniel H Huson.  Drawing Rooted Phylogenetic Networks.  IEEE/ACM Transactions on Computational Biology and Bioinformatics, 6(1):103–109, 2009.  doi:10.1109/TCBB.2008.58.
  * [24] Daniel H. Huson and David Bryant.  Application of Phylogenetic Networks in Evolutionary Studies.  Molecular Biology and Evolution, 23(2):254–267, 2005.  doi:10.1093/molbev/msj030.
  * [25] Daniel H Huson, Regula Rupp, and Celine Scornavacca.  Phylogenetic Networks: Concepts, Algorithms and Applications.  Cambridge University Press, 2010.
  * [26] Robin-Tobias Jauss, Nadiné Solf, Sree Rohit Raj Kolora, Stefan Schaffer, Ronny Wolf, Klaus Henle, Uwe Fritz, and Martin Schlegel.  Mitogenome evolution in the lacerta viridis complex (lacertidae, squamata) reveals phylogeny of diverging clades.  Systematics and Biodiversity, 19(7):682–692, 2021.  doi:10.1080/14772000.2021.1912205.
  * [27] Waqas Javed and Niklas Elmqvist.  Exploring the design space of composite visualization.  In Helwig Hauser, Stephen G. Kobourov, and Huamin Qu, editors, IEEE Pacific Visualization Symposium (PacificVis), pages 1–8, 2012.  doi:10.1109/PacificVis.2012.6183556.
  * [28] Monika Karmin, Rodrigo Flores, Lauri Saag, Georgi Hudjashov, Nicolas Brucato, Chelzie Crenna-Darusallam, Maximilian Larena, Phillip L Endicott, Mattias Jakobsson, J Stephen Lansing, Herawati Sudoyo, Matthew Leavesley, Mait Metspalu, François-Xavier Ricaut, and Murray P Cox.  Episodes of Diversification and Isolation in Island Southeast Asian and Near Oceanian Male Lineages.  Molecular Biology and Evolution, 39(3), 2022.  doi:10.1093/molbev/msac045.
  * [29] David M. Kidd and Xianhua Liu.  geophylobuilder 1.0: an arcgis extension for creating ‘geophylogenies’.  Molecular Ecology Resources, 8(1):88–91, 2008.  doi:10.1111/j.1471-8286.2007.01925.x.
  * [30] Jonathan Klawitter, Felix Klesen, Moritz Niederer, and Alexander Wolff.  Visualizing multispecies coalescent trees: Drawing gene trees inside species trees.  In Leszek Gasieniec, editor, SOFSEM 2023, volume 13878 of LNCS, pages 96–110. Springer, 2023.  doi:10.1007/978-3-031-23101-8_7.
  * [31] Jonathan Klawitter, Felix Klesen, Joris Y. Scholl, Thomas C. van Dijk, and Alexander Zaft.  Visualizing geophylogenies – internal and external labeling with phylogenetic tree constraints.  In Roger Beecham, Jed Long, Dianna Smith, Qunshan Zhao, and Sarah Wise, editors, GIScience, LIPIcs, 2023.  To appear.
  * [32] Jonathan Klawitter and Peter Stumpf.  Drawing tree-based phylogenetic networks with minimum number of crossings.  In David Auber and Pavel Valtr, editors, Graph Drawing and Network Visualization (GD), volume 12590 of LNCS, pages 173–180, 2020\.  doi:10.1007/978-3-030-68766-3_14.
  * [33] Chun-Cheng Lin, Hao-Jen Kao, and Hsu-Chun Yen.  Many-to-one boundary labeling.  Journal of Graph Algorithms and Applications, 12(3):319–356, 2008\.  doi:10.7155/jgaa.00169.
  * [34] Gabriele Neyer.  Map Labeling with Application to Graph Drawing, pages 247–273.  Springer, 2001.  doi:10.1007/3-540-44969-8_10.
  * [35] Benjamin Niedermann, Martin Nöllenburg, and Ignaz Rutter.  Radial contour labeling with straight leaders.  In Daniel Weiskopf, Yingcai Wu, and Tim Dwyer, editors, IEEE Pacific Visualization Symposium, pages 295–304. IEEE Computer Society, 2017\.  doi:10.1109/PACIFICVIS.2017.8031608.
  * [36] Roderic Page.  Visualising geophylogenies in web maps using geojson.  PLOS Currents, 7, 2015.  doi:10.1371/currents.tol.8f3c6526c49b136b98ec28e00b570a1e.
  * [37] Da Pan, Boyang Shi, Shiyu Du, Tianyu Gu, Ruxiao Wang, Yuhui Xing, Zhan Zhang, Jiajia Chen, Neil Cumberlidge, and Hongying Sun.  Mitogenome phylogeny reveals Indochina Peninsula origin and spatiotemporal diversification of freshwater crabs (Potamidae: Potamiscinae) in China.  Cladistics, 38(1):1–12, 2022.  doi:10.1111/cla.12475.
  * [38] Donovan H. Parks, Timothy Mankowski, Somayyeh Zangooei, Michael S. Porter, David G. Armanini, Donald J. Baird, Morgan G. I. Langille, and Robert G. Beiko.  Gengis 2: Geospatial analysis of traditional and genetic biodiversity, with new gradient algorithms and an extensible plugin framework.  PLoS ONE, 8(7):1–10, 2013.  doi:10.1371/journal.pone.0069885.
  * [39] Donovan H. Parks, Michael Porter, Sylvia Churcher, Suwen Wang, Christian Blouin, Jacqueline Whalley, Stephen Brooks, and Robert G. Beiko.  GenGIS: A geospatial information system for genomic data.  Genome Research, 19(10):1896–1904, 2009.  doi:10.1101/gr.095612.109.
  * [40] Andrew Rambaut.  Figtree v1.4, 2012.
  * [41] Liam J. Revell.  phytools: an r package for phylogenetic comparative biology (and other things).  Methods in Ecology and Evolution, 3(2):217–223, 2012.  doi:0.1111/j.2041-210X.2011.00169.x.
  * [42] Mike Steel.  Phylogeny: Discrete and Random Processes in Evolution.  Society for Industrial and Applied Mathematics, 2016.  doi:10.1137/1.9781611974485.
  * [43] Ray Tobler, Adam Rohrlach, Julien Soubrier, Pere Bover, Bastien Llamas, Jonathan Tuke, Nigel Bean, Ali Abdullah-Highfold, Shane Agius, Amy O’Donoghue, Isabel O’Loughlin, Peter Sutton, Fran Zilio, Keryn Walshe, Alan N. Williams, Chris S M Turney, Matthew Williams, Stephen M Richards, Robert J Mitchell, Emma Kowal, John R Stephen, Lesley Williams, Wolfgang Haak, and Alan Cooper.  Aboriginal mitogenomes reveal 50,000 years of regionalism in australia.  Nature, 544(7649):180–184, 2017.  doi:10.1038/nature21416.
  * [44] Ioannis G. Tollis and Konstantinos G. Kakoulis.  Algorithms for visualizing phylogenetic networks.  Theoretical Computer Science, 835:31–43, 2020.  doi:10.1016/j.tcs.2020.05.047.
  * [45] Jason T. Weir, Oliver Haddrath, Hugh A. Robertson, Rogan M. Colbourne, and Allan J. Baker.  Explosive ice age diversification of kiwi.  Proceedings of the National Academy of Sciences, 113(38):E5580–E5587, 2016.  doi:10.1073/pnas.1603795113.
  * [46] Trevor J. Williams and Jerald B. Johnson.  History predicts contemporary community diversity within a biogeographic province of freshwater fish.  Journal of Biogeography, 49(5):809–821, 2022.  doi:10.1111/jbi.14316.
  * [47] Xuhua Xia.  Pgt: Visualizing temporal and spatial biogeographic patterns.  Global Ecology and Biogeography, 28(8):1195–1199, 2019.  doi:10.1111/geb.12914.