Reconstruction of caterpillar tanglegrams

Ann Clifton; Éva Czabarka; Kevin Liu; Sarah Loeb; Utku Okur; László Székely; Kristina Wicke

doi:10.1016/j.dam.2025.09.022

Reconstruction of caterpillar tanglegrams

Ann Clifton
, Éva Czabarka
, Kevin Liu
, Sarah Loeb
, Utku Okur
, László Székely
, Kristina Wicke

Mathematical Sciences

Research output: Contribution to journal › Article › peer-review

Abstract

A tanglegram consists of two rooted binary trees with the same number of leaves and a perfect matching between the leaves of the trees. Given a size-n tanglegram, i.e., a tanglegram for two trees with n leaves, a multiset of induced size-(n−1) tanglegrams is obtained by deleting a pair of matched leaves in every possible way. Here, we analyze whether a size-n tanglegram is uniquely encoded by this multiset of size-(n−1) tanglegrams. We answer this question affirmatively in the case that at least one of the two trees of the tanglegram is a caterpillar tree.

Original language	English (US)
Pages (from-to)	647-661
Number of pages	15
Journal	Discrete Applied Mathematics
Volume	378
DOIs	https://doi.org/10.1016/j.dam.2025.09.022
State	Published - Jan 15 2026

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Applied Mathematics

Keywords

Caterpillar
Graph reconstruction
Rooted binary tree
Tanglegram

Access to Document

10.1016/j.dam.2025.09.022

Cite this

@article{37e156b9cf89420781bc00a1317a89cc,

title = "Reconstruction of caterpillar tanglegrams",

abstract = "A tanglegram consists of two rooted binary trees with the same number of leaves and a perfect matching between the leaves of the trees. Given a size-n tanglegram, i.e., a tanglegram for two trees with n leaves, a multiset of induced size-(n−1) tanglegrams is obtained by deleting a pair of matched leaves in every possible way. Here, we analyze whether a size-n tanglegram is uniquely encoded by this multiset of size-(n−1) tanglegrams. We answer this question affirmatively in the case that at least one of the two trees of the tanglegram is a caterpillar tree.",

keywords = "Caterpillar, Graph reconstruction, Rooted binary tree, Tanglegram",

author = "Ann Clifton and {\'E}va Czabarka and Kevin Liu and Sarah Loeb and Utku Okur and L{\'a}szl{\'o} Sz{\'e}kely and Kristina Wicke",

note = "Publisher Copyright: {\textcopyright} 2025 The Author(s)",

year = "2026",

month = jan,

day = "15",

doi = "10.1016/j.dam.2025.09.022",

language = "English (US)",

volume = "378",

pages = "647--661",

journal = "Discrete Applied Mathematics",

issn = "0166-218X",

publisher = "Elsevier B.V.",

}

TY - JOUR

T1 - Reconstruction of caterpillar tanglegrams

AU - Clifton, Ann

AU - Czabarka, Éva

AU - Liu, Kevin

AU - Loeb, Sarah

AU - Okur, Utku

AU - Székely, László

AU - Wicke, Kristina

PY - 2026/1/15

Y1 - 2026/1/15

N2 - A tanglegram consists of two rooted binary trees with the same number of leaves and a perfect matching between the leaves of the trees. Given a size-n tanglegram, i.e., a tanglegram for two trees with n leaves, a multiset of induced size-(n−1) tanglegrams is obtained by deleting a pair of matched leaves in every possible way. Here, we analyze whether a size-n tanglegram is uniquely encoded by this multiset of size-(n−1) tanglegrams. We answer this question affirmatively in the case that at least one of the two trees of the tanglegram is a caterpillar tree.

AB - A tanglegram consists of two rooted binary trees with the same number of leaves and a perfect matching between the leaves of the trees. Given a size-n tanglegram, i.e., a tanglegram for two trees with n leaves, a multiset of induced size-(n−1) tanglegrams is obtained by deleting a pair of matched leaves in every possible way. Here, we analyze whether a size-n tanglegram is uniquely encoded by this multiset of size-(n−1) tanglegrams. We answer this question affirmatively in the case that at least one of the two trees of the tanglegram is a caterpillar tree.

KW - Caterpillar

KW - Graph reconstruction

KW - Rooted binary tree

KW - Tanglegram

UR - https://www.scopus.com/pages/publications/105016588379

UR - https://www.scopus.com/pages/publications/105016588379#tab=citedBy

U2 - 10.1016/j.dam.2025.09.022

DO - 10.1016/j.dam.2025.09.022

M3 - Article

AN - SCOPUS:105016588379

SN - 0166-218X

VL - 378

SP - 647

EP - 661

JO - Discrete Applied Mathematics

JF - Discrete Applied Mathematics

ER -

Reconstruction of caterpillar tanglegrams

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this