Tree decomposition of Reeb graphs, parametrized complexity, and applications to phylogenetics (Q2195553)

A Reeb graph is a connected set \({\mathbb X}\) together with a real valued map \(f :\ {\mathbb X} \ \rightarrow \ {\mathbb R}\) which is strictly monotone when restricted to edges. Reeb graphs arise in computational phylogenetics. The main results of this paper show that a Reeb graph can be thought of as a coproduct of partially ordered trees. The author obtains results on the complexity of Reeb graphs and shows that the isomorphism problem is in a reasonable sense tractable.