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

被引：0
作者：
Stefanou A. [1 ]
机构：
[1] Mathematical Biosciences Institute, Department of Mathematics, The Ohio State University, Columbus, OH
来源：
Journal of Applied and Computational Topology | 2020年 / 4卷 / 2期
基金：
美国国家科学基金会;
关键词：
Betti number; Complexity; Coproducts; Decomposition; Phylogenetic networks; Reeb graphs;
D O I：
10.1007/s41468-020-00051-1
中图分类号：
学科分类号：
摘要：
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, can be identified with a coproduct of at most 2 s partially ordered trees with (n+ s) leaves. Reeb graphs are therefore classified up to isomorphism by their tree-decomposition. An implication of this result, is that the isomorphism problem for Reeb graphs is fixed parameter tractable when the parameter is the first Betti number. We propose partially ordered Reeb graphs as a model for time consistent phylogenetic networks and propose a certain Hausdorff distance as a metric on these structures. © 2020, Springer Nature Switzerland AG.
引用
收藏
页码：281 / 308
页数：27
相关论文
共 41 条
[11]  
Carlsson G., Zomorodian A., Collins A., Guibas L.J., Persistence barcodes for shapes, Int. J. Shape Model., 11, 2, pp. 149-187, (2005)
[12]  
Chazal F., Sun J., Gromov-Hausdorff Approximation of Metric Spaces with Linear Structure, (2013)
[13]  
Cohen-Steiner D., Edelsbrunner H., Harer J., Extending persistence using Poincaré and Lefschetz duality, Found. Comput. Math., 9, 1, pp. 79-103, (2009)
[14]  
Cole-McLaughlin K., Edelsbrunner H., Harer J., Natarajan V., Pascucci V., Loops in Reeb graphs of 2-manifolds, Discrete Comput. Geom., 32, 2, pp. 231-244, (2004)
[15]  
Crawley-Boevey W., Decomposition of pointwise finite-dimensional persistence modules, J. Algebra Appl., 14, 5, (2015)
[16]  
De Silva V., Munch E., Patel A., Categorified Reeb graphs, Discrete Comput. Geom., 55, 4, pp. 854-906, (2016)
[17]  
Dey T.K., Fan F., Wang Y., An efficient computation of handle and tunnel loops via Reeb graphs, ACM Trans. Gr. (TOG), 32, 4, (2013)
[18]  
Di Fabio B., Landi C., The edit distance for Reeb graphs of surfaces, Discrete Comput. Geom., 55, 2, pp. 423-461, (2016)
[19]  
Dress A., The category of x-nets, Networks: From Biology to Theory, pp. 3-22, (2007)
[20]  
Edelsbrunner H., Harer J., Patel A.K., Reeb spaces of piecewise linear mappings, Symposium on Computational Geometry, pp. 242-250, (2008)
12345