Geodesic
Characterizing planar tanglegram layouts and applications to edge insertion problems
Kevin Liu1
1University of Washington Department of Mathematics
The electronic journal of combinatorics, Tome 30 (2023) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

Tanglegrams are formed by taking two rooted binary trees $T$ and $S$ with the same number of leaves and uniquely matching each leaf in $T$ with a leaf in $S$. They are usually represented using layouts that embed the trees and matching in the plane. Given the numerous ways to construct a layout, one problem of interest is the Tanglegram Layout Problem, which is to efficiently find a layout that minimizes the number of crossings. This parallels a similar problem involving drawings of graphs, where a common approach is to insert edges into a planar subgraph. In this paper, we explore inserting edges into a planar tanglegram. Previous results on planar tanglegrams include a Kuratowski Theorem, enumeration, and an algorithm for finding a planar layout. We build on these results and characterize all planar layouts of a planar tanglegram. We then apply this characterization to construct a quadratic-time algorithm that inserts a single edge optimally. Finally, we generalize some results to multiple edge insertion.
DOI : 10.37236/11299
Classification : 05C05, 05C10, 05C30
Mots-clés : rooted binary trees, tanglegram layout problem

Kevin Liu  1

1 University of Washington Department of Mathematics 
@article{10_37236_11299,
     author = {Kevin Liu},
     title = {Characterizing planar tanglegram layouts and applications to edge insertion problems},
     journal = {The electronic journal of combinatorics},
     year = {2023},
     volume = {30},
     number = {2},
     doi = {10.37236/11299},
     zbl = {1516.05028},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/11299/}
}
TY  - JOUR
AU  - Kevin Liu
TI  - Characterizing planar tanglegram layouts and applications to edge insertion problems
JO  - The electronic journal of combinatorics
PY  - 2023
VL  - 30
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/11299/
DO  - 10.37236/11299
ID  - 10_37236_11299
ER  - 
%0 Journal Article
%A Kevin Liu
%T Characterizing planar tanglegram layouts and applications to edge insertion problems
%J The electronic journal of combinatorics
%D 2023
%V 30
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/11299/
%R 10.37236/11299
%F 10_37236_11299
Kevin Liu. Characterizing planar tanglegram layouts and applications to edge insertion problems. The electronic journal of combinatorics, Tome 30 (2023) no. 2. doi: 10.37236/11299

Cité par Sources :