Classes of tree-based networks

Mareike Fischer, Michelle Galla, Lina Herbst, Yangjing Long, Kristina Wicke

Research output: Contribution to journalArticlepeer-review

4 Scopus citations

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 languageEnglish (US)
Article number12
JournalVisual Computing for Industry, Biomedicine, and Art
Volume3
Issue number1
DOIs
StatePublished - Dec 2020
Externally publishedYes

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

Fingerprint

Dive into the research topics of 'Classes of tree-based networks'. Together they form a unique fingerprint.

Cite this