Scholarlink

<p>Tanglegrams are drawings of two rooted binary phylogenetic trees and a matching between their leaf sets. The trees are drawn crossing-free on opposite sides with their leaf sets facing each other on two vertical lines. Instead of minimizing the number of pairwise edge crossings, we consider the problem of minimizing the number of <i>block crossings</i>, that is, two bundles of edges crossing each other locally. With one tree fixed, the leaves of the second tree can be permuted according to its tree structure. We give a complete picture of the algorithmic complexity of minimizing block crossings in one-sided tanglegrams by showing <Emphasis FontCategory="SansSerif">NP</Emphasis>-completeness, 2.25-approximations, and a fixed-parameter algorithm with the parameter being the number of block crossings of the computed tanglegram. We also state results for non-binary trees.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Block Crossings in One-Sided Tanglegrams

  • 期刊论文

  • 出版模式：

    开放获取

  • 发表日期：

    2026年2月7日

查看全文
  • Alexander Dobler,
  • Martin Nöllenburg

摘要

Tanglegrams are drawings of two rooted binary phylogenetic trees and a matching between their leaf sets. The trees are drawn crossing-free on opposite sides with their leaf sets facing each other on two vertical lines. Instead of minimizing the number of pairwise edge crossings, we consider the problem of minimizing the number of block crossings, that is, two bundles of edges crossing each other locally. With one tree fixed, the leaves of the second tree can be permuted according to its tree structure. We give a complete picture of the algorithmic complexity of minimizing block crossings in one-sided tanglegrams by showing NP-completeness, 2.25-approximations, and a fixed-parameter algorithm with the parameter being the number of block crossings of the computed tanglegram. We also state results for non-binary trees.