Séminaire Lotharingien de Combinatoire, 86B.45 (2022), 12 pp.

Kevin Liu

Planar Tanglegram Layouts and Single Edge Insertion

Abstract. 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. Planar tanglegrams are tanglegrams that have a layout with no crossings. Previous work on planar tanglegrams include enumeration, a Tanglegram Kuratowski Theorem, and an algorithm for drawing a planar layout. In this paper, we characterize all planar layouts of a planar tanglegram. We then apply our work to inserting a single edge into a planar tanglegram.

Received: November 25, 2021. Accepted: March 4, 2022. Final version: April 1, 2022.

The following versions are available:

PDF (172 K)
TeX version