Abstract
Recently, so-called tree-based phylogenetic networks have attracted considerable attention. These networks can be constructed from a phylogenetic tree, called the base tree, by adding additional edges. The primary aim of this study is to provide sufficient criteria for tree-basedness by reducing phylogenetic networks to related graph structures. Even though it is generally known that determining whether a network is tree-based is an NP-complete problem, one of these criteria, namely edge-basedness, can be verified in linear time. Surprisingly, the class of edge-based networks is closely related to a well-known family of graphs, namely, the class of generalized series-parallel graphs, and we explore this relationship in full detail. Additionally, we introduce further classes of tree-based networks and analyze their relationships.
| Original language | English (US) |
|---|---|
| Article number | 12 |
| Journal | Visual Computing for Industry, Biomedicine, and Art |
| Volume | 3 |
| Issue number | 1 |
| DOIs | |
| State | Published - Dec 2020 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- Software
- Computer Science (miscellaneous)
- Medicine (miscellaneous)
- Visual Arts and Performing Arts
- Computer Vision and Pattern Recognition
- Computer Graphics and Computer-Aided Design
Keywords
- Chordal network
- Edge-based network
- Generalized series-parallel graphs
- Hamilton connected
- Hamiltonian path
- Phylogenetic network
- Phylogenetic tree
- Series-parallel graphs
- Tree-based network