{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,16]],"date-time":"2025-10-16T00:17:34Z","timestamp":1760573854358,"version":"build-2065373602"},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"5","license":[{"start":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T00:00:00Z","timestamp":1758931200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T00:00:00Z","timestamp":1758931200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100008678","name":"Universit\u00e4t Leipzig","doi-asserted-by":"crossref","id":[{"id":"10.13039\/501100008678","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2025,10]]},"abstract":"<jats:title>Abstract<\/jats:title>\n          <jats:p>Arboreal networks are a generalization of rooted trees, defined by keeping the tree-like structure, but dropping the requirement for a single root. Just as the class of cographs is precisely the class of undirected graphs that can be explained by a labelled rooted tree (<jats:italic>T<\/jats:italic>,\u00a0<jats:italic>t<\/jats:italic>), we show that the class of distance-hereditary graphs is precisely the class of undirected graphs that can be explained by a labelled arboreal network (<jats:italic>N<\/jats:italic>,\u00a0<jats:italic>t<\/jats:italic>).<\/jats:p>","DOI":"10.1007\/s00373-025-02977-8","type":"journal-article","created":{"date-parts":[[2025,9,27]],"date-time":"2025-09-27T14:44:35Z","timestamp":1758984275000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Representing distance-hereditary graphs with multi-rooted trees"],"prefix":"10.1007","volume":"41","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-5033-8040","authenticated-orcid":false,"given":"Guillaume E.","family":"Scholz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,9,27]]},"reference":[{"key":"2977_CR1","doi-asserted-by":"publisher","DOI":"10.1371\/journal.pcbi.1000262","volume":"5","author":"AM Altenhoff","year":"2009","unstructured":"Altenhoff, A.M., Dessimoz, C.: Phylogenetic and functional assessment of orthologs inference projects and methods. PLoS Comput. Biol. 5, e1000262 (2009)","journal-title":"PLoS Comput. Biol."},{"key":"2977_CR2","doi-asserted-by":"publisher","first-page":"182","DOI":"10.1016\/0095-8956(86)90043-2","volume":"41","author":"HJ Bandelt","year":"1986","unstructured":"Bandelt, H.J., Mulder, H.M.: Distance-hereditary graphs. J. Combin. Theory Ser. B 41, 182\u2013208 (1986)","journal-title":"J. Combin. Theory Ser. B"},{"key":"2977_CR3","doi-asserted-by":"publisher","DOI":"10.1137\/1.9780898719796","volume-title":"Graph Classes: A Survey","author":"A Brandst\u00e4dt","year":"1999","unstructured":"Brandst\u00e4dt, A., Le, V.B., Spinrad, J.P.: Graph Classes: A Survey. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA (1999)"},{"key":"2977_CR4","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1016\/j.dam.2021.12.017","volume":"310","author":"C Bruckmann","year":"2022","unstructured":"Bruckmann, C., Stadler, P., Hellmuth, M.: From modular decomposition trees to rooted median graphs. Discret. Appl. Math. 310, 1\u20139 (2022)","journal-title":"Discret. Appl. Math."},{"key":"2977_CR5","first-page":"163","volume":"3","author":"DG Corneil","year":"1981","unstructured":"Corneil, D.G., Lerchs, H., Stewart Burlingham, L.K.: Complement reducible graphs. discr. Appl. Math. 3, 163\u2013174 (1981)","journal-title":"Appl. Math."},{"issue":"4","key":"2977_CR6","doi-asserted-by":"publisher","first-page":"926","DOI":"10.1137\/0214065","volume":"14","author":"DG Corneil","year":"1985","unstructured":"Corneil, D.G., Perl, Y., Stewart, L.K.: A linear recognition algorithm for cographs. SIAM J. Comput. 14(4), 926\u2013934 (1985)","journal-title":"SIAM J. Comput."},{"key":"2977_CR7","doi-asserted-by":"crossref","unstructured":"Crespelle, C., Gras, B., Perez, A.: Completion to chordal distance-hereditary graphs: a quartic vertex-kernel. WG 2021: Graph-Theoretic Concepts in Computer Science pp. 156\u2013168 (2021)","DOI":"10.1007\/978-3-030-86838-3_12"},{"key":"2977_CR8","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/S0304-3975(00)00234-6","volume":"263","author":"G Damiand","year":"2001","unstructured":"Damiand, G., Habib, M., Paul, C.: A simple paradigm for graph recognition: application to cographs and distance-hereditary graphs. Theoret. Comput. Sci. 263, 99\u2013111 (2001)","journal-title":"Theoret. Comput. Sci."},{"key":"2977_CR9","doi-asserted-by":"crossref","unstructured":"Di Stefano, G.: Distance-hereditary comparability graphs. Discrete Applied Mathematics 160(18), 2669\u20132680 (2012). V Latin American Algorithms, Graphs, and Optimization Symposium \u2014 Gramado, Brazil, 2009","DOI":"10.1016\/j.dam.2012.02.021"},{"issue":"4","key":"2977_CR10","doi-asserted-by":"publisher","first-page":"1250004.1","DOI":"10.1142\/S0219720012500047","volume":"10","author":"P Gambette","year":"2012","unstructured":"Gambette, P., Berry, V., Paul, C.: Quartets and unrooted phylogenetic networks. Journal of Bioinformatics and Computational Biology 10(4), 1250004.1-1250004..23 (2012)","journal-title":"Journal of Bioinformatics and Computational Biology"},{"issue":"7","key":"2977_CR11","doi-asserted-by":"publisher","first-page":"1729","DOI":"10.1007\/s00285-016-1068-3","volume":"74","author":"P Gambette","year":"2017","unstructured":"Gambette, P., Huber, K., Kelk, S.: On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters. J. Math. Biol. 74(7), 1729\u20131751 (2017)","journal-title":"J. Math. Biol."},{"issue":"23","key":"2977_CR12","doi-asserted-by":"publisher","first-page":"2763","DOI":"10.1016\/j.disc.2013.08.017","volume":"313","author":"Y Gao","year":"2013","unstructured":"Gao, Y., Hare, D.R., Nastos, J.: The cluster deletion problem for cographs. Discret. Math. 313(23), 2763\u20132771 (2013)","journal-title":"Discret. Math."},{"issue":"6","key":"2977_CR13","doi-asserted-by":"publisher","first-page":"708","DOI":"10.1016\/j.dam.2011.05.007","volume":"160","author":"E Gioan","year":"2012","unstructured":"Gioan, E., Paul, C.: Split decomposition and graph-labelled trees: characterizations and fully dynamic algorithms for totally decomposable graphs. Discret. Appl. Math. 160(6), 708\u2013733 (2012)","journal-title":"Discret. Appl. Math."},{"key":"2977_CR14","doi-asserted-by":"crossref","unstructured":"Gusfield, D., Eddhu, S., Langley, C.: Efficient reconstruction of phylogenetic networks with constrained recombination. CSB \u201903: Proceedings of the IEEE Computer Society Conference on Bioinformatics pp. 363\u2013374 (2003)","DOI":"10.1109\/CSB.2003.1227337"},{"issue":"1","key":"2977_CR15","doi-asserted-by":"publisher","first-page":"85","DOI":"10.1016\/0166-218X(90)90131-U","volume":"27","author":"PL Hammer","year":"1990","unstructured":"Hammer, P.L., Maffray, F.: Completely separable graphs. Discret. Appl. Math. 27(1), 85\u201399 (1990)","journal-title":"Discret. Appl. Math."},{"issue":"1\u20132","key":"2977_CR16","doi-asserted-by":"publisher","first-page":"399","DOI":"10.1007\/s00285-012-0525-x","volume":"66","author":"M Hellmuth","year":"2013","unstructured":"Hellmuth, M., Hernandez-Rosales, M., Huber, K.T., Moulton, V., Stadler, P.F., Wieseke, N.: Orthology relations, symbolic ultrametrics, and cographs. J. Math. Biology 66(1\u20132), 399\u2013420 (2013)","journal-title":"J. Math. Biology"},{"key":"2977_CR17","doi-asserted-by":"publisher","DOI":"10.1007\/s12064-023-00398-w","author":"M Hellmuth","year":"2023","unstructured":"Hellmuth, M., Schaller, D., Stadler, P.F.: Clustering systems of phylogenetic networks. Theory Biosci. (2023). https:\/\/doi.org\/10.1007\/s12064-023-00398-w","journal-title":"Theory Biosci."},{"key":"2977_CR18","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.dam.2022.06.042","volume":"321","author":"M Hellmuth","year":"2022","unstructured":"Hellmuth, M., Scholz, G.E.: From modular decomposition trees to level-1 networks: pseudo-cographs, polar-cats and prime polar-cats. Discret. Appl. Math. 321, 179\u2013219 (2022)","journal-title":"Discret. Appl. Math."},{"key":"2977_CR19","doi-asserted-by":"publisher","first-page":"25","DOI":"10.1016\/j.dam.2023.09.034","volume":"343","author":"M Hellmuth","year":"2023","unstructured":"Hellmuth, M., Scholz, G.E.: Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs. Discret. Appl. Math. 343, 25\u201343 (2023)","journal-title":"Discret. Appl. Math."},{"key":"2977_CR20","doi-asserted-by":"publisher","first-page":"115","DOI":"10.1007\/978-3-031-49190-0_8","volume":"1442","author":"M Hellmuth","year":"2024","unstructured":"Hellmuth, M., Scholz, G.E.: Linear time algorithms for NP-hard problems restricted to GaTEx graphs. Computing and Combinatorics (COCOON 2023). Lecture Notes in Computer Sciences 1442, 115\u2013126 (2024)","journal-title":"Lecture Notes in Computer Sciences"},{"key":"2977_CR21","doi-asserted-by":"crossref","unstructured":"Hellmuth, M., Wieseke, N.: From sequence data including orthologs, paralogs, and xenologs to gene and species trees. Evolutionary Biology: Convergent Evolution, Evolution of Complex Traits, Concepts and Methods pp. 373\u2013392 (2016)","DOI":"10.1007\/978-3-319-41324-2_21"},{"issue":"7","key":"2977_CR22","doi-asserted-by":"publisher","first-page":"2058","DOI":"10.1073\/pnas.1412770112","volume":"112","author":"M Hellmuth","year":"2015","unstructured":"Hellmuth, M., Wieseke, N., Lechner, M., Lenhof, H.P., Middendorf, M., Stadler, P.F.: Phylogenomics with paralogs. Proc. Natl. Acad. Sci. 112(7), 2058\u20132063 (2015)","journal-title":"Proc. Natl. Acad. Sci."},{"issue":"Suppl 19","key":"2977_CR23","doi-asserted-by":"publisher","first-page":"S6","DOI":"10.1186\/1471-2105-13-S19-S6","volume":"13","author":"M Hernandez-Rosales","year":"2012","unstructured":"Hernandez-Rosales, M., Hellmuth, M., Wieseke, N., Huber, K.T., Moulton, V., Stadler, P.F.: From event-labeled gene trees to species trees. BMC Bioinformatics 13(Suppl 19), S6 (2012)","journal-title":"BMC Bioinformatics"},{"issue":"28","key":"2977_CR24","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1093\/qmath\/28.4.417","volume":"2","author":"E Howorka","year":"1977","unstructured":"Howorka, E.: A characterization of distance-hereditary graphs. Quart. J. Math. Oxford, Ser. 2(28), 417\u2013420 (1977)","journal-title":"Quart. J. Math. Oxford, Ser."},{"key":"2977_CR25","doi-asserted-by":"publisher","first-page":"323","DOI":"10.1002\/jgt.3190050314","volume":"5","author":"E Howorka","year":"1981","unstructured":"Howorka, E.: A characterization of ptolemaic graphs. J. Graph Theory 5, 323\u2013321 (1981)","journal-title":"J. Graph Theory"},{"issue":"10","key":"2977_CR26","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1007\/s11538-022-01081-9","volume":"84","author":"KT Huber","year":"2022","unstructured":"Huber, K.T., Moulton, V., Scholz, G.E.: Forest-based networks. Bull. Math. Biol. 84(10), 119 (2022)","journal-title":"Bull. Math. Biol."},{"issue":"4","key":"2977_CR27","doi-asserted-by":"publisher","first-page":"2553","DOI":"10.1137\/23M1573318","volume":"38","author":"KT Huber","year":"2024","unstructured":"Huber, K.T., Moulton, V., Scholz, G.E.: Shared ancestry graphs and symbolic arboreal maps. SIAM J. Discret. Math. 38(4), 2553\u20132577 (2024)","journal-title":"SIAM J. Discret. Math."},{"issue":"1","key":"2977_CR28","doi-asserted-by":"publisher","first-page":"73","DOI":"10.1007\/s00453-016-0241-9","volume":"80","author":"KT Huber","year":"2018","unstructured":"Huber, K.T., Scholz, G.E.: Beyond representing orthology relations by trees. Algorithmica 80(1), 73\u2013103 (2018)","journal-title":"Algorithmica"},{"key":"2977_CR29","doi-asserted-by":"publisher","first-page":"342","DOI":"10.4153\/CJM-1965-034-0","volume":"17","author":"DC Kay","year":"1965","unstructured":"Kay, D.C., Chartrand, G.: A characterization of certain ptolemaic graphs. Canad. J. Math. 17, 342\u2013346 (1965)","journal-title":"Canad. J. Math."},{"issue":"1","key":"2977_CR30","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1186\/s13015-016-0067-7","volume":"11","author":"M Lafond","year":"2016","unstructured":"Lafond, M., Dondi, R., El-Mabrouk, N.: The link between orthology relations and gene trees: a correction perspective. Algorithms for Molecular Biology 11(1), 1 (2016)","journal-title":"Algorithms for Molecular Biology"},{"issue":"6","key":"2977_CR31","doi-asserted-by":"publisher","first-page":"S12","DOI":"10.1186\/1471-2164-15-S6-S12","volume":"15","author":"M Lafond","year":"2014","unstructured":"Lafond, M., El-Mabrouk, N.: Orthology and paralogy constraints: satisfiability and consistency. BMC Genomics 15(6), S12 (2014)","journal-title":"BMC Genomics"},{"key":"2977_CR32","doi-asserted-by":"crossref","unstructured":"Lafond, M., El-Mabrouk, N.: Orthology relation and gene tree correction: complexity results. International Workshop on Algorithms in Bioinformatics pp. 66\u201379 (2015)","DOI":"10.1007\/978-3-662-48221-6_5"},{"issue":"1","key":"2977_CR33","doi-asserted-by":"publisher","first-page":"54","DOI":"10.1016\/j.mbs.2009.06.007","volume":"221","author":"F Rossello","year":"1965","unstructured":"Rossello, F., Valiente, G.: All that glisters is not galled. Math. Bioisci. 221(1), 54\u201359 (1965)","journal-title":"Math. Bioisci."},{"issue":"5","key":"2977_CR34","doi-asserted-by":"publisher","first-page":"717","DOI":"10.1093\/sysbio\/syz004","volume":"68","author":"GE Scholz","year":"2019","unstructured":"Scholz, G.E., Popescu, A.A., Taylor, M.I., Moulton, V., Huber, K.T.: Osf-builder: a new tool for constructing and representing evolutionary histories involving introgression. Syst. Biol. 68(5), 717\u2013729 (2019)","journal-title":"Syst. Biol."},{"issue":"2","key":"2977_CR35","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1016\/0095-8956(74)90063-X","volume":"16","author":"D Seinsche","year":"1974","unstructured":"Seinsche, D.: On a property of the class of n-colorable graphs. Journal of Combinatorial Theory, Series B 16(2), 191\u2013193 (1974)","journal-title":"Journal of Combinatorial Theory, Series B"},{"issue":"4","key":"2977_CR36","doi-asserted-by":"publisher","first-page":"492","DOI":"10.1017\/S1446788700029232","volume":"18","author":"DP Sumner","year":"1974","unstructured":"Sumner, D.P.: Dacey graphs. J. Aust. Math. Soc. 18(4), 492\u2013502 (1974)","journal-title":"J. Aust. Math. Soc."},{"issue":"7","key":"2977_CR37","doi-asserted-by":"publisher","first-page":"1533","DOI":"10.1016\/j.dam.2008.09.006","volume":"157","author":"R Uehara","year":"2009","unstructured":"Uehara, R., Uno, Y.: Laminar structure of ptolemaic graphs with applications. Discret. Appl. Math. 157(7), 1533\u20131543 (2009)","journal-title":"Discret. Appl. Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02977-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00373-025-02977-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-025-02977-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,15]],"date-time":"2025-10-15T05:11:32Z","timestamp":1760505092000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00373-025-02977-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,9,27]]},"references-count":37,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,10]]}},"alternative-id":["2977"],"URL":"https:\/\/doi.org\/10.1007\/s00373-025-02977-8","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2025,9,27]]},"assertion":[{"value":"8 January 2024","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"21 September 2025","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"27 September 2025","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no conflict of interest.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflicts of Interest"}}],"article-number":"111"}}