{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,16]],"date-time":"2026-05-16T13:00:16Z","timestamp":1778936416882,"version":"3.51.4"},"reference-count":23,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T00:00:00Z","timestamp":1589500800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T00:00:00Z","timestamp":1589500800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Vis. Comput. Ind. Biomed. Art"],"published-print":{"date-parts":[[2020,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>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.<\/jats:p>","DOI":"10.1186\/s42492-020-00043-z","type":"journal-article","created":{"date-parts":[[2020,5,15]],"date-time":"2020-05-15T14:15:24Z","timestamp":1589552124000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["Classes of tree-based networks"],"prefix":"10.1186","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-9429-0859","authenticated-orcid":false,"given":"Mareike","family":"Fischer","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michelle","family":"Galla","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Lina","family":"Herbst","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yangjing","family":"Long","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4275-5546","authenticated-orcid":false,"given":"Kristina","family":"Wicke","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,5,15]]},"reference":[{"issue":"5","key":"43_CR1","doi-asserted-by":"publisher","first-page":"768","DOI":"10.1093\/sysbio\/syv037","volume":"64","author":"AR Francis","year":"2015","unstructured":"Francis AR, Steel M (2015) Which phylogenetic networks are merely trees with additional arcs? Syst Biol 64(5):768\u2013777. https:\/\/doi.org\/10.1093\/sysbio\/syv037","journal-title":"Syst Biol"},{"issue":"2","key":"43_CR2","doi-asserted-by":"publisher","first-page":"404","DOI":"10.1007\/s11538-017-0381-3","volume":"80","author":"A Francis","year":"2018","unstructured":"Francis A, Huber KT, Moulton V (2018) Tree-based unrooted phylogenetic networks. Bull Math Biol 80(2):404\u2013416. https:\/\/doi.org\/10.1007\/s11538-017-0381-3","journal-title":"Bull Math Biol"},{"issue":"1","key":"43_CR3","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1109\/TCBB.2016.2615918","volume":"15","author":"L Jetten","year":"2018","unstructured":"Jetten L, van Iersel L (2018) Nonbinary tree-based phylogenetic networks. IEEE\/ACM Trans Comput Biol Bioinform 15(1):205\u2013217. https:\/\/doi.org\/10.1109\/TCBB.2016.2615918","journal-title":"IEEE\/ACM Trans Comput Biol Bioinform"},{"key":"43_CR4","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/j.mbs.2018.06.005","volume":"302","author":"M Hendriksen","year":"2018","unstructured":"Hendriksen M (2018) Tree-based unrooted nonbinary phylogenetic networks. Math Biosci 302:131\u2013138. https:\/\/doi.org\/10.1016\/j.mbs.2018.06.005","journal-title":"Math Biosci"},{"key":"43_CR5","volume-title":"Non-binary treebased unrooted phylogenetic networks and their relations to binary and rooted ones","author":"M Fischer","year":"2018","unstructured":"Fischer M, Galla M, Herbst L, Long YJ, Wicke K (2018) Non-binary treebased unrooted phylogenetic networks and their relations to binary and rooted ones. arXiv:1810.06853"},{"key":"43_CR6","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/11415770_17","volume-title":"Research in computational molecular biology. 9th annual international conference, RECOMB 2005, May 2005. Lecture notes in computer science","author":"D Gusfield","year":"2005","unstructured":"Gusfield D, Bansal V (2005) A fundamental decomposition theory for phylogenetic networks and incompatible characters. In: Miyano S, Mesirov J, Kasif S, Istrail S, Pevzner PA, Waterman M (eds) Research in computational molecular biology. 9th annual international conference, RECOMB 2005, May 2005. Lecture notes in computer science, vol 3500. Springer, Berlin, Heidelberg, pp 217\u2013232. https:\/\/doi.org\/10.1007\/11415770_17"},{"issue":"3","key":"43_CR7","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1016\/0012-365X(73)90138-6","volume":"5","author":"V Chv\u00e1tal","year":"1973","unstructured":"Chv\u00e1tal V (1973) Tough graphs and hamiltonian circuits. Discret Math 5(3):215\u2013228. https:\/\/doi.org\/10.1016\/0012-365X(73)90138-6","journal-title":"Discret Math"},{"key":"43_CR8","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/j.jctb.2016.07.002","volume":"122","author":"A Kabela","year":"2017","unstructured":"Kabela A, Kaiser T (2017) 10-tough chordal graphs are Hamiltonian. J Comb Theory, Ser B 122:417\u2013427. https:\/\/doi.org\/10.1016\/j.jctb.2016.07.002","journal-title":"J Comb Theory, Ser B"},{"key":"43_CR9","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53622-3","volume-title":"Graph theory","author":"R Diestel","year":"2017","unstructured":"Diestel R (2017) Graph theory, 5th edn. Springer, Berlin, Heidelberg. https:\/\/doi.org\/10.1007\/978-3-662-53622-3","edition":"5"},{"key":"43_CR10","doi-asserted-by":"publisher","first-page":"479","DOI":"10.1145\/1993636.1993700","volume-title":"Proceedings of the 43rd annual ACM symposium on theory of computing","author":"M Grohe","year":"2011","unstructured":"Grohe M, Kawarabayashi KI, Marx D, Wollan P (2011) Finding topological subgraphs is fixed-parameter tractable. In: Proceedings of the 43rd annual ACM symposium on theory of computing. ACM, San Jose, pp 479\u2013488. https:\/\/doi.org\/10.1145\/1993636.1993700"},{"key":"43_CR11","doi-asserted-by":"publisher","first-page":"407","DOI":"10.1007\/3-540-49164-3_40","volume":"15","author":"CW Ho","year":"1999","unstructured":"Ho CW, Hsieh SY, Chen GH (1999) Parallel decomposition of generalized series-parallel graphs. J Inf Sci Eng 15:407\u2013417. https:\/\/doi.org\/10.1007\/3-540-49164-3_40","journal-title":"J Inf Sci Eng"},{"key":"43_CR12","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1007\/978-1-4684-2001-2_9","volume-title":"Complexity of computer computations","author":"RM Karp","year":"1972","unstructured":"Karp RM (1972) Reducibility among combinatorial problems. In: Miller RE, Thatcher JW, Bohlinger JD (eds) Complexity of computer computations. Springer, Boston, pp 85\u2013103. https:\/\/doi.org\/10.1007\/978-1-4684-2001-2_9"},{"key":"43_CR13","doi-asserted-by":"publisher","first-page":"487","DOI":"10.1016\/s0167-5060(08)70484-9","volume":"41","author":"RJ Wilson","year":"1988","unstructured":"Wilson RJ (1988) A brief history of hamiltonian graphs. Ann Dis Math 41:487\u2013496. https:\/\/doi.org\/10.1016\/s0167-5060(08)70484-9","journal-title":"Ann Dis Math"},{"issue":"1","key":"43_CR14","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1016\/j.ipl.2004.12.002","volume":"94","author":"MS Rahman","year":"2005","unstructured":"Rahman MS, Kaykobad M (2005) On Hamiltonian cycles and Hamiltonian paths. Inf Process Lett 94(1):37\u201341. https:\/\/doi.org\/10.1016\/j.ipl.2004.12.002","journal-title":"Inf Process Lett"},{"issue":"1","key":"43_CR15","doi-asserted-by":"publisher","first-page":"116","DOI":"10.1016\/j.aml.2005.10.024","volume":"20","author":"KW Zhao","year":"2007","unstructured":"Zhao KW, Lai HJ, Shao YH (2007) New sufficient condition for Hamiltonian graphs. Appl Math Lett 20(1):116\u2013122. https:\/\/doi.org\/10.1016\/j.aml.2005.10.024","journal-title":"Appl Math Lett"},{"issue":"2","key":"43_CR16","doi-asserted-by":"publisher","first-page":"130","DOI":"10.1002\/jgt.20099","volume":"50","author":"ZQ Hu","year":"2005","unstructured":"Hu ZQ, Tian F, Wei B (2005) Hamilton connectivity of line graphs and claw-free graphs. J Graph Theory 50(2):130\u2013141. https:\/\/doi.org\/10.1002\/jgt.20099","journal-title":"J Graph Theory"},{"issue":"1","key":"43_CR17","doi-asserted-by":"publisher","first-page":"21","DOI":"10.26493\/1855-3974.291.574","volume":"6","author":"B Alspach","year":"2013","unstructured":"Alspach B (2013) Johnson graphs are Hamilton-connected. Ars Math Contemp 6(1):21\u201323. https:\/\/doi.org\/10.26493\/1855-3974.291.574","journal-title":"Ars Math Contemp"},{"key":"43_CR18","first-page":"161","volume":"63","author":"TV Wimer","year":"1988","unstructured":"Wimer TV, Hedetniemi ST (1988) K-terminal recursive families of graphs. Congr Numer 63:161\u2013176","journal-title":"Congr Numer"},{"issue":"6","key":"43_CR19","doi-asserted-by":"publisher","first-page":"372","DOI":"10.1145\/362248.362272","volume":"16","author":"J Hopcroft","year":"1973","unstructured":"Hopcroft J, Tarjan R (1973) Algorithm 447: efficient algorithms for graph manipulation. Commun ACM 16(6):372\u2013378. https:\/\/doi.org\/10.1145\/362248.362272","journal-title":"Commun ACM"},{"issue":"2","key":"43_CR20","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1137\/0211023","volume":"11","author":"J Valdes","year":"1982","unstructured":"Valdes J, Tarjan RE, Lawler EL (1982) The recognition of series parallel digraphs. SIAM J Comput 11(2):298\u2013313. https:\/\/doi.org\/10.1137\/0211023","journal-title":"SIAM J Comput"},{"issue":"1-2","key":"43_CR21","doi-asserted-by":"publisher","first-page":"311","DOI":"10.1016\/j.dam.2012.07.018","volume":"161","author":"G Brinkmann","year":"2013","unstructured":"Brinkmann G, Coolsaet K, Goedgebeur J, M\u00e9lot H (2013) House of graphs: a database of interesting graphs. Discret Appl Math 161(1-2):311\u2013314. https:\/\/doi.org\/10.1016\/j.dam.2012.07.018","journal-title":"Discret Appl Math"},{"key":"43_CR22","doi-asserted-by":"publisher","first-page":"457","DOI":"10.1007\/978-3-540-72588-6_75","volume-title":"Computational science - ICCS 2007. 7th international conference, May 2007. Lecture notes in computer science","author":"HM Song","year":"2007","unstructured":"Song HM, Wu JL, Liu GZ (2007) The equitable edge-coloring of series-parallel graphs. In: Shi Y, van Albada GD, Dongarra J, Sloot PMA (eds) Computational science - ICCS 2007. 7th international conference, May 2007. Lecture notes in computer science, vol 4489. Springer, Berlin, pp 457\u2013460. https:\/\/doi.org\/10.1007\/978-3-540-72588-6_75"},{"key":"43_CR23","volume-title":"Mathematica, version 10.3","author":"Wolfram Research, Inc","year":"2017","unstructured":"Wolfram Research, Inc (2017) Mathematica, version 10.3. Wolfram Research, Inc, Champaign"}],"updated-by":[{"DOI":"10.1186\/s42492-021-00069-x","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2021,1,26]],"date-time":"2021-01-26T00:00:00Z","timestamp":1611619200000}}],"container-title":["Visual Computing for Industry, Biomedicine, and Art"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42492-020-00043-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42492-020-00043-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42492-020-00043-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,5,14]],"date-time":"2021-05-14T23:08:52Z","timestamp":1621033732000},"score":1,"resource":{"primary":{"URL":"https:\/\/vciba.springeropen.com\/articles\/10.1186\/s42492-020-00043-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,5,15]]},"references-count":23,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2020,12]]}},"alternative-id":["43"],"URL":"https:\/\/doi.org\/10.1186\/s42492-020-00043-z","relation":{"correction":[{"id-type":"doi","id":"10.1186\/s42492-021-00069-x","asserted-by":"object"}]},"ISSN":["2524-4442"],"issn-type":[{"value":"2524-4442","type":"electronic"}],"subject":[],"published":{"date-parts":[[2020,5,15]]},"assertion":[{"value":"12 September 2019","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"17 February 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 May 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 January 2021","order":4,"name":"change_date","label":"Change Date","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"Correction","order":5,"name":"change_type","label":"Change Type","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"An amendment to this paper has been published and can be accessed via the original article.","order":6,"name":"change_details","label":"Change Details","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"The authors declare that they have no competing interests.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"12"}}