Anastasios Stefanou
Inspired by the interval decomposition of persistence modules and the extended Newick format of phylogenetic networks, we show that, inside the larger category of partially ordered Reeb graphs, every Reeb graph with n leaves and first Betti number s, is equal to a coproduct of at most 2s trees with (n+s) leaves. An implication of this result, is that Reeb graphs are fixed parameter tractable when the parameter is the first Betti number. We propose partially ordered Reeb graphs as a natural framework for modeling time consistent phylogenetic networks. Furthermore, we define an interleaving distance on partially ordered Reeb graphs. Originated in Topological Data Analysis, the notion of interleaving distance can be defined on an arbitrary category with a notion of a flow. In contrast with other metrics for phylogenetic networks, the interleaving distance gives us the ability to compare a pair of time consistent phylogenetic networks having, either different labelings on their leaves, or having some of their leaves labeled, or a combination of both, where the labelings are viewed as a partial order on the vertex set of the network. When the partial orders of a pair of Reeb graphs are trivial (no labeling) we obtain the interleaving distance for ordinary Reeb graphs.
