2 Preliminaries
In this section we present some notation that will be needed to describe the NeighborNet algorithm. We will assume some basic facts concerning phylogenetic trees, more details concerning which may be found in [11].
Throughout this paper, X will denote a finite set with cardinality n. A split S = {A, B} (of X) is a bipartition of X. We let Ϭ = Ϭ(X) = {{A, X\A}Ø ⊂ A ⊂ X} denote the set of all splits of X, and call any nonempty subset of Ϭ(X) a split system. A split weight function on X is a map ω: Ϭ(X) → _{≥0}. We let Ϭ_{ω }denote the set {S ∈ Ϭω(S) > 0}, the support of ω.
Let Θ = x_{1}, ..., x_{n }be an ordering of X. A split S = {A, B} is compatible with Θ if there exist i, j ∈ {1, ..., n}, i ≤ j, such that A = {x_{i}, ..., x_{j}} or B = {x_{i}, ..., x_{j}}. Note that if a split is compatible with an ordering Θ it is also compatible with its reversal x_{n}, ..., x_{2}, x_{1 }and with ordering x_{2}, ..., x_{n}, x_{1}. We let Ϭ_{Θ }denote the set of those splits in Ϭ(X) which are compatible with ordering Θ. A split system Ϭ' is compatible with Θ if Ϭ' ⊆ Ϭ_{Θ}. In addition a split system Ϭ' ⊆ Ϭ(X) is circular if there exists an ordering Θ of X such that Ϭ' is compatible with Θ. Note that any split system corresponding to a phylogenetic tree is circular [[11], Ch. 3], and so circular split systems can be regarded as a generalization of split systems induced by phylogenetic trees. A split weight function ω is called circular if the split system Ϭ_{ω }is circular. A distance function on X is a map d: X × X → _{≥0 }such that for all x, y ∈ X both d(x, x) = 0 and d(x, y) = d(y, x) hold. Note that any split weight function ω on X induces a distance function d_{ω }on X as follows: For a split S = {A, B} ∈ Ϭ(X) define the distance function or split metric d_{S }by


and put
for all x, y ∈ X. A distance function d is called circular if there exits a circular split weight function ω such that d = d_{ω}. An ordering Θ of X is said to be compatible with d if there exists ω such that d = d_{ω }and Ϭ_{ω }⊆ Ϭ_{Θ. }Note that the representation of a circular distance function d is unique, i.e., if d = and d = for circular split weight functions ω_{1 }and ω_{2 }then ω_{1 }= ω_{2 }holds [10].
Circular distances were introduced in [10] and have been further studied in, for example, [12] and [13]. Just as any treelike distance function on X can be uniquely represented by a phylogenetic tree [[11], ch. 7], any circular distance function d can be represented by a planar phylogenetic network such as the one pictured in Figure 1[14]. The program SplitsTree [9] allows the automatic generation of such a network for d by computing a circular split weight function ω with d = d_{ω}.