Representing non-crossing cuts by phylogenetic trees - Thomas Lange (GTA Research Group, Univ. Newcastle, Indonesian Combinatorics Society and ITB, 2021)
Phylogenetic trees are representations of the evolutionary descendency of a set of species. In graph-theoretic terms, a phylogenetic tree is a partially labeled tree where unlabeled vertices have at least degree three and labels corresponds to pairwise disjoint subsets of the set of species. A cut of a graph G = (V, E) is defined as bipartition S, V S of the vertex set V of G. A pair of cuts S, S, T, T is said to be crossing, if neither S ∩ T, S ∩ T, S ∩ T nor S ∩ T is empty. In this paper, we show that each set of pairwise non-crossing cuts of a graph G can be represented uniquely by a phylogenetic tree such that the set of species corresponds to the vertex set of G.