  Attempting to recognize a tree inside a phylogenetic network is a fundamental
undertaking in evolutionary analysis. In the last few years, therefore,
tree-based phylogenetic networks, which are defined by a spanning tree called a
subdivision tree, have attracted attention of theoretical biologists. However,
the application of such networks is still not easy, due to many problems whose
time complexities are not clearly understood. In this paper, we provide a
general framework for solving those various old or new problems from a coherent
perspective, rather than analyzing the complexity of each individual problem or
developing an algorithm one by one. More precisely, we establish a structure
theorem that gives a way to canonically decompose any rooted binary
phylogenetic network N into maximal zig-zag trails that are uniquely
determined, and use it to characterize the set of subdivision trees of N in the
form of a direct product, in a way reminiscent of the structure theorem for
finitely generated Abelian groups. From the main results, we derive a series of
linear time and linear time delay algorithms for the following problems: given
a rooted binary phylogenetic network N, 1) determine whether or not N has a
subdivision tree and find one if there exists any; 2) measure the deviation of
N from being tree-based; 3) compute the number of subdivision trees of N; 4)
list all subdivision trees of N; and 5) find a subdivision tree to maximize or
minimize a prescribed objective function. All algorithms proposed here are
optimal in terms of time complexity. Our results do not only imply and unify
various known results, but also answer many open questions and moreover enable
novel applications, such as the estimation of a maximum likelihood tree
underlying a tree-based network. The results and algorithms in this paper still
hold true for a special class of rooted non-binary phylogenetic networks.
