论文标题
表征平面缠结的布局和应用到边缘插入问题的应用
Characterizing Planar Tanglegram Layouts and Applications to Edge Insertion Problems
论文作者
论文摘要
缠结是通过服用两根二进制树$ t $和$ s $具有相同叶子的叶子，并以$ t $中的叶子与$ s $中的叶子搭配的每片叶子的唯一匹配。它们通常使用布局表示，将树嵌入树木和叶子匹配到平面中，如图1所示。鉴于构造布局的多种方法，感兴趣的一个问题是缠结布局问题，即有效地找到一个将交叉数量最小化的布局。这与涉及图的图纸的类似问题相似，其中一种常见的方法是将边缘插入平面子图中。在本文中，我们将探索将边缘插入平面缠结。平面缠结的先前结果包括kuratowski定理，枚举和用于绘制平面布局的算法。我们首先基于这些结果并表征平面缠结的所有平面布局。然后，我们将此表征应用于构造最佳插入单个边缘的二次时间算法。最后，我们将一些结果推广到多个边插入。
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, which embed the trees and the matching of the leaves into the plane as in Figure 1. 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 will explore inserting edges into a planar tanglegram. Previous results on planar tanglegrams include a Kuratowski Theorem, enumeration, and an algorithm for drawing a planar layout. We start by building on these results and characterizing 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.
