%% if you are submitting an initial manuscript then you should have submission as an option here
%% if you are submitting a revised manuscript then you should have revision as an option here
%% otherwise options taken by the article class will be accepted
\documentclass[final]{FPSAC2022}
%% but DO NOT pass any options (or change anything else anywhere) which alters page size / layout / font size etc

%\usepackage{lipsum}

%% note that the class file already loads {amsmath, amsthm, amssymb}

\usepackage{mathrsfs}
\usepackage{amsfonts}
\usepackage{mathtools}
\usepackage{graphics}
\usepackage{graphicx}
%\usepackage{enumerate}
%\usepackage{enumitem}
\usepackage[linesnumbered,ruled,vlined]{algorithm2e}
\usepackage{tikz}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{problem}[theorem]{Problem}
%\newtheorem*{problem*}{Problem}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{example}[theorem]{Example}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}



\usepackage{comment}
%\usepackage[backend=bibtex,style=numeric]{biblatex}
\addbibresource{bibliography.bib}
%\bibliographystyle{plain}
%\renewbibmacro{in:}{}

%\usepackage{lineno}
%\linenumbers
\newcommand{\algname}[1]{\texttt{#1}}
\newcommand{\xmt}[1]{\xmapsto{#1}}
\newcommand{\op}[1]{\operatorname{#1}}
\DeclareMathOperator{\leaf}{\operatorname{Lf}}
\DeclareMathOperator{\cross}{\operatorname{Crs}}
\DeclareMathOperator{\rut}{\operatorname{root}}
\DeclareMathOperator{\crt}{\operatorname{crt}}
\DeclareMathOperator{\crtei}{\operatorname{crtei}}



\begin{document}

\title{Planar Tanglegram Layouts and Single Edge Insertion}
\author[K.~Liu]{Kevin Liu\thanks{\href{mailto:kliu15@uw.edu}{kliu15@uw.edu}. Partially supported by the National Science Foundation grant DMS-1764012.}\addressmark{1}}%\footnote{The author was partially supported by the National Science Foundation grant DMS-1764012.}}
\received{November 24, 2021}
\keywords{tanglegram, tree, layout, crossing, planar, edge insertion}
\address{\addressmark{1}Department of Mathematics, University of Washington, Seattle, WA 98125, USA}

\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.}



\maketitle

\vspace{-6pt}
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.6925]
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\draw[dashed] (-1,2) -- (1,-1);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,-2);
\draw[dashed] (-1,-1) -- (1,2);
\draw[dashed] (-1,-2) -- (1,0);
\draw (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-1.5,1.5) -- (-2,1) -- (-1,0) -- (-2,1) -- (-3,0) -- (-1,-2) -- (-1.5,-1.5) -- (-1,-1);
\draw (1,2) -- (2,1) --(1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0) -- (1.5,0.5) -- (2,1) -- (2.5,.5) -- (1,-1) -- (2.5,.5)-- (3,0) -- (1,-2);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,1) circle (1pt);
\filldraw[fill=black,draw=black] (-3,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (2,1) circle (1pt);
\filldraw[fill=black,draw=black] (3,0) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,0.5) circle (1pt);
\node at (-1,2.325) {\small{$t_1$}};
\node at (-1,1.325) {\small{$t_2$}};
\node at (-1,0.325) {\small{$t_3$}};
\node at (-1,-0.625) {\small{$t_4$}};
\node at (-1,-1.625) {\small{$t_5$}};
\node at (1,2.325) {\small{$s_1$}};
\node at (1,1.325) {\small{$s_2$}};
\node at (1,0.325) {\small{$s_3$}};
\node at (1,-0.625) {\small{$s_4$}};
\node at (1,-1.625) {$s_5$};
\end{tikzpicture}\qquad
\begin{tikzpicture}[scale=0.6925]
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\draw[dashed] (-1,2) -- (1,2);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw (-1,0) -- (-1.5,0.5) -- (-1,1) -- (-1.5,0.5) -- (-2,1) -- (-1,2) -- (-2,1) -- (-3,0) -- (-1,-2) -- (-1.5,-1.5) -- (-1,-1);
\draw (1,1) -- (2.5,-0.5) -- (2,-1) -- (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) -- (2,-1) -- (1,-2) -- (3,0) -- (1,2);
\filldraw[fill=black,draw=black] (-1.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,1) circle (1pt);
\filldraw[fill=black,draw=black] (-3,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (2,-1) circle (1pt);
\filldraw[fill=black,draw=black] (3,0) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-0.5) circle (1pt);
\node at (-1,2.325) {$t_3$};
\node at (-1,1.325) {$t_1$};
\node at (-1,0.325) {$t_2$};
\node at (-1,-0.625) {$t_5$};
\node at (-1,-1.625) {$t_4$};
\node at (1,2.325) {$s_5$};
\node at (1,1.325) {$s_4$};
\node at (1,0.325) {$s_2$};
\node at (1,-0.625) {$s_3$};
\node at (1,-1.625) {$s_1$};
\end{tikzpicture}
    \caption{Two layouts for the same tanglegram.}\label{tanglegramexample}
    \end{center}\vspace{-24pt}
\end{figure}

\vspace{-6pt}
%\vspace{-24pt}

\section{Introduction}

Let $T$ and $S$ be two rooted binary trees with leaves labeled as $\{t_i\}_{i\in I}$ and $\{s_j\}_{j\in J}$, respectively, where $I,J\subseteq \mathbb{N}$ are finite index sets of the same size. If we let $\phi\colon I\to J$ be a bijection, then we can denote a tanglegram as $(T,S,\phi)$, where $\phi$ indicates that $t_i$ is matched with $s_{\phi(i)}$. %Usually, we will let $I$ and $J$ be $[n]=\{1,2,\ldots ,n\}$, so assume that this is the case unless otherwise specified. Note that tanglegrams are considered up to isomorphisms of the underlying trees, so relabeling vertices or applying automorphisms of the trees do not produce a new tanglegram. 
A \textit{layout} of a tanglegram draws $T$, $S$, and the edges $(t_i,s_{\phi(i)})$ in the plane such that $T$ is planarly embedded left of the line $x=0$ with all leaves on $x=0$, $S$ is planarly embedded right of the line $x=1$ with all leaves on $x=1$, and the edges $(t_i,s_{\phi(i)})$ are drawn using straight lines. Examples are shown in Figure \ref{tanglegramexample}.
A \textit{crossing} is any pair of edges $(t_i,s_{\phi(i)})$ and $(t_j,s_{\phi(j)})$ that intersect in the layout, and the \textit{crossing number} of a tanglegram $(T,S,\phi)$, denoted $\crt(T,S,\phi)$, is the minimum number of crossings over all layouts of $(T,S,\phi)$. The Tanglegram Layout Problem attempts to efficiently find a layout that achieves the crossing number.

Tanglegrams initially arose in biology and computer science. Biologists use binary trees to model evolution and tanglegrams to model relationships between species. Finding optimal layouts helps determine how two species may have co-evolved \cite{reduction}.  Applications in computer science include clustering, decomposition of programs into layers, or analyzing the difference in hierarchy between similar programs or different versions of the same program \cite{algorithm}. Combinatorial interest in tanglegrams developed more recently. Matsen \textit{et al.}~\cite{reduction} formalized tanglegrams as mathematical objects and described connections with phylogenetics. Billey, Konvalinka, and Matsen \cite{count} enumerated tanglegrams and constructed an algorithm to generate them uniformly at random. Subsequently, Ralaivaosaona, Ravelomanana, and Wagner counted planar tanglegrams \cite{countingplanar}, Gessel counted several variations of tanglegrams using combinatorial species \cite{species}, and Konvalinka and Wagner studied the properties of random tanglegrams \cite{randomtanglegram}.

The Tanglegram Layout Problem has connections to the problem of drawing a graph with the fewest number of crossings possible. The crossing number of a graph $G$, denoted $\operatorname{cr}(G)$, is the minimum number of crossings over all drawings of $G$. Determining if $\operatorname{cr}(G)\leq k$ for some $k\in \mathbb{N}$ is NP-complete \cite{CNNP}, and the same is true for determining if $\crt(T,S,\phi)\leq k$ \cite{tlhard}.
Known results in graph drawings sometimes have analogous results in tanglegram layouts, and some have approached the Tanglegram Layout Problem by translating known results about graphs to tanglegrams.  Czabarka, Sz\'ekely, and Wagner recently constructed a Tanglegram Kuratowski Theorem characterizing planar tanglegrams. Previously, Lozano \textit{et al.}\ constructed an algorithm for drawing a planar layout \cite{layout}. Anderson \textit{et al.}\ recently translated results in graph drawings to prove that removing a between-tree edge $(t_i,s_{\phi(i)})$ from a tanglegram reduces crossing number by at most $n-3$, and they produce a family of tanglegrams to show that this bound is sharp \cite{analogy}.

Given the difficulty of minimizing crossings in graph drawings, some have studied approximating $\operatorname{cr}(G)$ rather than finding it exactly. One approach to this is edge insertion. The Edge Insertion Problem for graphs starts with a graph $G$ and an edge $e \in G$ such that $G\setminus\{e\}$ is planar, and attempts to find a drawing of $G$ in the plane so that the drawing of $G\setminus \{e\}$ is planar and the number of crossings from $e$ is minimized. This problem  is well studied. A linear-time algorithm exists to solve it, and some bounds have been found relating an optimal drawing of $G$ and a solution to the Edge Insertion Problem for $G\setminus \{e\}$ with $\{e\}$ inserted \cite{insert1,almostplanar}.
The Edge Insertion Problem generalizes to the Multiple Edge Insertion Problem, where we insert several edges $\{e_1,\ldots ,e_n\}$ into planar $G\setminus \{e_1,\ldots,e_n\}$ optimally, and current approximation algorithms for $\operatorname{cr}(G)$ still use multiple edge insertion with planar subgraphs \cite{graphcrossing}. Given the role that edge insertion with planar subgraphs plays in graph drawing, it is plausible that edge insertion can play a similar role for tanglegram layouts.
\newpage 
In this paper, we outline several results involving planar tanglegram layouts and single edge insertion. Full details for these results and their proofs can be found in \cite{liu2022}. We start by characterizing the planar layouts of a planar tanglegram. For a planar tanglegram $(T,S,\phi)$, we will define a \textit{leaf-matched pair} $(u,v)$ as a pair of internal vertices $u\in T$ and $v\in S$ whose descendant leaves are matched by $\phi$, and we will define an operation called a \textit{paired flip}. By adding steps to the \algname{Untangle} algorithm by Lozano \textit{et al.}\ for drawing a planar layout of a planar tanglegram, we construct \algname{ModifiedUntangle} (Algorithm \ref{modifieduntangle}), which also identifies leaf-matched pairs and stores them in a set $L$, obtaining the following result. 


\begin{theorem}\label{planarlayouts}
 Let $(T,S,\phi)$ be a planar tanglegram, and let $\mathscr{P}(T,S,\phi)$ denote its collection of planar layouts. Let the output of $\algname{ModifiedUntangle}(T,S,\phi)$ be the layout $(X,Y)$ and set of leaf-matched pairs $L$. Every $(X',Y')\in \mathscr{P}(T,S,\phi)$ can be obtained by starting with $(X,Y)$ and performing a sequence of paired flips at $(u,v)\in L$.
 %Starting with $(X,Y)$, paired flips of leaf-matched vertices produce all planar layouts of $(T,S,\phi)$. 
\end{theorem}

Note that when $T$ and $S$  have more than one vertex, the roots of $T$ and $S$ always form a leaf-matched pair of $(T,S,\phi)$. If this is the only leaf-matched pair, then we call the tanglegram \textit{irreducible}. Letting $\text{size}(T,S,\phi)$ be the common number of leaves in $T$ and $S$, the generating function
\begin{equation}\label{Hx}
        H(x) = \sum_{\text{irreducible planar $(T,S,\phi)$}} x^{\text{size}(T,S,\phi)} \\
\end{equation}
was studied in \cite{countingplanar}, where the authors used the convention that the coefficient of $x^2$ is $\frac{1}{2}$ to obtain their results enumerating planar tanglegrams. We maintain this convention. If
\begin{equation}\label{Fxq}
\begin{split}
    F(x,q) & =\sum_{\text{planar  }(T,S,\phi)}x^{\text{size}(T,S,\phi)}q^{|\{\text{leaf-matched pairs of $(T,S,\phi)$}\}|},
\end{split}
\end{equation}
then the coefficient of $x^nq^k$ counts the number of planar tanglegrams of size $n$ with $k$ leaf-matched pairs. The following result allows us to find these coefficients.

%The roots of $T$ and $S$ are 
%\textcolor{red}{move irreducible and Hx definition up here and say it was studied in RRW paper}
%We then generalize previous work on counting planar tanglegrams. Using the generating function $H(x)$ and results from \cite{countingplanar}, we obtain the following theorem, which allows us to count the number of planar tanglegrams with $k$ leaf-matched pairs.
%\textcolor{red}{move Fxq outside of the theorem and have Hx beside it}
%Define

\begin{theorem}\label{lmpcount}
The generating function $F(x,q)$ satisfies the relation
\[F(x,q)=q\cdot H(F(x,q))+x+\frac{q\cdot F(x^2,q^2)}{2}.\]
\end{theorem}


Finally, we consider the tanglegram analogue of (single) edge insertion, which we state below. Using our previous results on leaf-matched pairs, we will describe our \algname{Insertion} algorithm for efficiently solving this problem.


\begin{problem}[Tanglegram Single Edge Insertion]
Given a tanglegram $(T,S,\phi)$ and a planar subtanglegram $(T_I,S_{\phi(I)},\phi|_I)$ induced by the index set $I=[n]\setminus \{i\}$ for $i\in [n]$, find a layout of $(T,S,\phi)$ that restricts to a planar layout of $(T_I,S_{\phi(I)},\phi|_I)$ and has the minimal number of crossings possible.
\end{problem}


\begin{theorem}\label{insertiontheorem}
The \algname{Insertion} Algorithm solves the Tanglegram  Single Edge Insertion Problem in $O(n^2)$ time and space, where $n$ is the size of the tanglegram.
\end{theorem}





%\textcolor{red}{LATER: advertise some specific theorems around here; edit the previous paragraph. Some candidates:
%\begin{itemize}
 %   \item Theorem \ref{planarlayouts} (every planar layout can be obtained from a sequence of paired flips starting with the output from \algname{ModifiedUntangle})
  %  \item Theorem \ref{insertiontime} (\algname{Insertion} solves Tanglegram Edge Insertion in $O(n^2)$ time and space)
   % \item Maybe add theorem about TEI and TL problems having arbitrarily large difference 
    %\item Theorem \ref{NP-hard} (multiple edge insertion is NP-hard), be careful this is not overlapping with other previous results 
    %\item Theorem \ref{iteratedinsertion} (\algname{IteratedInsertion} finds a layout with at most $|I|\cdot (2n-|I|-5)/2$ crossings in $O(|I|\cdot n^2)$ time)
%\end{itemize}}

%In this paper, we translate edge insertion for graphs into analogous problems for tanglegrams. 
%We start in Section \ref{background} by outlining some terminology, notation, and previous results. In Section \ref{planar}, we extend previous results on planar tanglegrams by characterizing all planar layouts of a planar tanglegram and giving an efficient method for obtaining these planar layouts. In Section \ref{TEI}, we define the Tanglegram Edge Insertion Problem and provide an algorithm that solves it in quadratic time with respect to the number of leaves in each tree. Then we apply this algorithm to almost planar tanglegrams, where removal of a single edge results in a planar tanglegram. Paralleling results in graph drawings, we show that the solution to the Tanglegram Edge Insertion Problem for almost planar tanglegrams does not necessarily correspond to a solution to the Tanglegram Layout Problem.  In Section \ref{MEI}, we define the Tanglegram Multiple Edge Insertion Problem. We show that similar to Multiple Edge Insertion for graph drawings, this problem is NP-hard. We then use our results from Section \ref{TEI} to construct an algorithm that is efficient when the number of inserted edges is small. We conclude by discussing future work in Section \ref{future}.

\section{Preliminaries}\label{background}

A \textit{rooted binary tree} $T$ is a tree in which every vertex has either zero or two children, and where a designated vertex called the root, denoted $\rut(T)$, is allowed to have degree 2. A vertex that has children is called an \textit{internal vertex}, and a vertex with no children is called a \textit{leaf}. If $v$ has children $v_1$ and $v_2$, we call $v$ the parent of $v_1$ and $v_2$. 
We say that a vertex $v_1$ is a \textit{descendant} of $v_k$ or $v_k$ is an \textit{ancestor} of $v_1$ if there is a sequence of vertices $v_1,v_2,\ldots ,v_k$ such that $v_{i+1}$ is the parent of $v_i$ for  $i=1,2,\ldots, k-1$, and we use the notation $v_1<v_k$ or $v_k>v_1$ to denote this. When needed, we will use a subscript with the name of a tree to indicate ancestry in specific trees, such as $v_k>_T v_1$. 

For an internal vertex $v\in T$, the \textit{subtree rooted at $v$} is the tree formed by all vertices $u$ with $u\leq v$, and this subtree then has $v$ as its root. Using subtrees, we can represent trees using the nested lists notation from Section 2.3.2 of \cite{knuth}. Each set of parenthesis represents a subtree, and the label for the root of this subtree is written to the left of the parenthesis. Unless otherwise stated, we will index leaves with $[n]=\{1,2,\ldots ,n\}$, and usually we will omit labels for internal vertices. 
%All trees are considered up to isomorphism, so relabeling vertices does not produce a new tree. 

All trees are considered up to isomorphism, so relabeling vertices does not produce a different tree. Given an internal vertex $v\in T$, a \textit{flip} at vertex $v$ is the operation that interchanges the order of the children for all $u\leq v$. Pictorially, if we start with a drawing of a tree $T$, a flip at $v\in T$ reflects the subtree rooted at $v$, which motivates the name ``flip.'' Note that for any tree $T$, flips generate all trees isomorphic to $T$.
%Note that flips generate all automorphisms of a tree.
%In particular, notice that the flip operation at $v$ reverses the order of all leaves in the subtree rooted at $v$. 

Tanglegrams $(T,S,\phi)$ are formed from a pair of rooted binary trees $T,S$ and a bijection $\phi$ matching their leaves. The \textit{size} of the tanglegram $(T,S,\phi)$ is the common number of leaves in $T$ or $S$. We will call the edges in $T$ and $S$ \textit{tree edges} and call the edges induced by $\phi$ \textit{between-tree edges}. For any vertex $u\in T$ or $v\in S$, we will use $\leaf(u)$ and $\leaf (v)$ to respectively denote the set of leaves that are descendants of $u$ in $T$ and the descendants of $v$ in $S$. As with trees, we consider tanglegrams up to isomorphism. Since flips generate all trees isomorphic to the underlying trees, they also generate all tanglegrams isomorphic to a given tanglegram.

Our notation for tanglegram layouts builds on the notation used in \cite{layout}. In any layout, the number of crossings is completely determined by the order of the leaves in the two trees and the bijection $\phi$ matching these leaves, as the between-tree edges $(t_i,s_{\phi(i)})$ and $(t_j,s_{\phi(j)})$ intersect when $t_i$ is embedded above $t_j$ and $s_{\phi(i)}$ is embedded below $s_{\phi(j)}$. Since we are primarily interested in the number of crossings rather than specific coordinates of the plane embedding, we give the following definition.

\begin{definition}
Let $(T,S,\phi)$ be a tanglegram drawn in the plane with a given layout. The \textit{leaf order} of the given layout is a pair of ordered lists $(X,Y)$, where $X$ and $Y$ respectively list the leaves of $T$ and $S$ in order of appearance from top to bottom in the layout.
%Let $(T,S,\phi)$ be a tanglegram, and let $f\colon (T,S,\phi)\to \mathbb{R}^2$ be a tanglegram layout. The \textit{leaf order of $f$} is a pair of ordered lists $(X,Y)$, where $X$ and $Y$ respectively list the leaves of $T$ and $S$ in order of appearance from top to bottom in $f(T,S,\phi)$.
\end{definition}

One can view the leaf order of a layout $(X,Y)$ as an equivalence class of layouts, where two layouts are equivalent if they draw the leaves of $T$ and $S$ in the same order from top to bottom. To recover a layout from the ordered lists $(X,Y)$, one can draw the leaves listed in $X$ and $Y$ from top to bottom respectively on $x=0$ and $x=1$, and then use the information from $T$, $S$, and $\phi$ to draw the trees and between-tree edges. Flips generate all trees isomorphic to $T$ or $S$, so they can act on leaf orders $(X,Y)$ to obtain all possible leaf orders, where a flip at an internal vertex $u$ acts on $(X,Y)$ by reversing the order of the elements in $\leaf(u)$ in the appropriate list $X$ or $Y$. Throughout this paper, we abuse terminology and refer to this pair of lists $(X,Y)$ also as a tanglegram layout.

Finally, we will define induced subtrees and induced subtanglegrams using a similar definition as in \cite{kura}. Notice that layouts $(X',Y')$ of subtanglegrams correspond to taking sub-lists in layouts $(X,Y)$ of the original tanglegram.

\begin{definition}\label{subtreedefinition}
Let $T$ be a tree with leaves indexed by $[n]$. For any $I\subseteq [n]$, the \textit{rooted binary subtree induced by $I$}, denoted $T_I$, is formed by taking the minimal subtree of $T$ containing the leaves indexed by $I$ and suppressing all internal vertices that have only one child.
For a tanglegram $(T,S,\phi)$ with leaves indexed by $[n]$, the \textit{subtanglegram induced by $I$} is the tanglegram $(T_I,S_{\phi(I)},\phi|_I)$, that is, the tanglegram formed from the induced subtrees $T_I$ and $S_{\phi(I)}$ with leaves matched using the restriction $\phi|_I$. 
%$T_I$ to be the unique minimal subtree of $T$ containing all of the vertices in $I$. \textcolor{red}{check what other people defined, maybe say take the smallest subtree containing those vertices, and then smooth all internal vertices that are not needed?}
\end{definition}
%\begin{definition}\label{subtanglegramdefinition}
%Let $(T,S,\phi)$ be a tanglegram with the leaves of $T$ and $S$ indexed by $[n]$. For any $I\subseteq [n]$, the \textit{induced subtanglegram by $I$} is the tanglegram $(T_I,S_{\phi(I)},\phi|_I)$, that is, the tanglegram formed from the induced subtrees $T_I$ and $S_{\phi(I)}$ with leaves matched using the restriction $\phi|_I$. 
%\end{definition}

\begin{example}\label{layoutexample}
Consider the tanglegram $(T,S,\phi)$ shown on the left in Figure \ref{notation} with
\begin{center}
%\vspace{-4pt}
    $T=(((t_1,t_2),t_3),(t_4,t_5))$ \quad $S=(((s_1,(s_2,s_3)),s_4),s_5)$ \quad 
    \begin{tabular}{c|c|c|c|c|c}
    $i$ & $1$ & $2$ & $3$ & $4$ & $5$ \\
    \hline
    $\phi(i)$ & $4$ & $2$ & $5$ & $1$ & $3$ 
\end{tabular}
%\vspace{-4pt}
\end{center}


By writing the leaves of $T$ and $S$ in the order given, we obtain the layout $(X,Y)=(t_1t_2t_3t_4t_5,s_1s_2s_3s_4s_5)$. A flip at the root of $((s_1,(s_2,s_3)),s_4)$ yields $(t_1t_2t_3t_4t_5,s_4s_3s_2s_1s_5)$. Taking sub-lists of $(t_1t_2t_3t_4t_5,s_4s_3s_2s_1s_5)$ based on the elements in the sets $\{1,2,4,5\}$ and $\phi(\{1,2,4,5\})$, we obtain the layout $(t_1t_2t_4t_5,s_4s_3s_2s_1)$ for $(T_{\{1,2,4,5\}},S_{\phi(\{1,2,4,5\})},\phi|_{\{1,2,4,5\}})$. Using $T$ and $S$, we produce the drawings in Figure \ref{notation} corresponding to these sequences.
\end{example}

\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.6]
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\draw[dashed] (-1,2) -- (1,-1);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,-2);
\draw[dashed] (-1,-1) -- (1,2);
\draw[dashed] (-1,-2) -- (1,0);
\draw (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-1.5,1.5) -- (-2,1) -- (-1,0) -- (-2,1) -- (-3,0) -- (-1,-2) -- (-1.5,-1.5) -- (-1,-1);
\draw (1,2) -- (2,1) --(1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0) -- (1.5,0.5) -- (2,1) -- (2.5,.5) -- (1,-1) -- (2.5,.5)-- (3,0) -- (1,-2);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,1) circle (1pt);
\filldraw[fill=black,draw=black] (-3,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (2,1) circle (1pt);
\filldraw[fill=black,draw=black] (3,0) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,0.5) circle (1pt);
\node at (-1,2.325) {\small{$t_1$}};
\node at (-1,1.325) {\small{$t_2$}};
\node at (-1,0.325) {\small{$t_3$}};
\node at (-1,-0.625) {\small{$t_4$}};
\node at (-1,-1.625) {\small{$t_5$}};
\node at (1,2.325) {\small{$s_1$}};
\node at (1,1.325) {\small{$s_2$}};
\node at (1,0.325) {\small{$s_3$}};
\node at (1,-0.625) {\small{$s_4$}};
\node at (1,-1.625) {\small{$s_5$}};
%\node at (2.5,0.75) {$v$};

%%%%

\filldraw[fill=black,draw=black] (6,2) circle (1pt);
\filldraw[fill=black,draw=black] (6,1) circle (1pt);
\filldraw[fill=black,draw=black] (6,0) circle (1pt);
\filldraw[fill=black,draw=black] (6,-1) circle (1pt);
\filldraw[fill=black,draw=black] (6,-2) circle (1pt);
\filldraw[fill=black,draw=black] (8,2) circle (1pt);
\filldraw[fill=black,draw=black] (8,1) circle (1pt);
\filldraw[fill=black,draw=black] (8,0) circle (1pt);
\filldraw[fill=black,draw=black] (8,-1) circle (1pt);
\filldraw[fill=black,draw=black] (8,-2) circle (1pt);
\draw[dashed] (6,2) -- (8,2);
\draw[dashed] (6,1) -- (8,0);
\draw[dashed] (6,0) -- (8,-2);
\draw[dashed] (6,-1) -- (8,-1);
\draw[dashed] (6,-2) -- (8,1);
\draw (6,2) -- (5.5,1.5) -- (6,1) -- (5.5,1.5) -- (5,1) -- (6,0) -- (5,1) -- (4,0) -- (6,-2) -- (5.5,-1.5) -- (6,-1);
\draw (8,2) -- (9.5,0.5) -- (9,0) -- (8,1) -- (8.5,0.5) -- (8,0) -- (8.5,0.5) -- (9,0) -- (8,-1) -- (9.5,0.5) -- (10,0) -- (8,-2);
\filldraw[fill=black,draw=black] (5.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (5,1) circle (1pt);
\filldraw[fill=black,draw=black] (4,0) circle (1pt);
\filldraw[fill=black,draw=black] (5.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (8.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (9,0) circle (1pt);
\filldraw[fill=black,draw=black] (10,0) circle (1pt);
\filldraw[fill=black,draw=black] (9.5,0.5) circle (1pt);
\node at (6,2.325) {\small{$t_1$}};
\node at (6,1.325) {\small{$t_2$}};
\node at (6,0.325) {\small{$t_3$}};
\node at (6,-0.625) {\small{$t_4$}};
\node at (6,-1.625) {\small{$t_5$}};
\node at (8,2.325) {\small{$s_4$}};
\node at (8,1.325) {\small{$s_3$}};
\node at (8,0.325) {\small{$s_2$}};
\node at (8,-0.625) {\small{$s_1$}};
\node at (8,-1.625) {\small{$s_5$}};
%\node at (9.5,0.75) {$v$};

%%%%%

\filldraw[fill=black,draw=black] (12.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (12.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (12.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (12.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (14.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (14.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (14.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (14.5,-1.5) circle (1pt);
\node at (12.5,1.875) {\small{$t_1$}};
\node at (12.5,0.875) {\small{$t_2$}};
\node at (12.5,-0.125) {\small{$t_4$}};
\node at (12.5,-1.125) {\small{$t_5$}};
\node at (14.5,1.875) {\small{$s_4$}};
\node at (14.5,0.875) {\small{$s_3$}};
\node at (14.5,-0.125) {\small{$s_2$}};
\node at (14.5,-1.125) {\small{$s_1$}};
\draw[dashed] (12.5,1.5) -- (14.5,1.5);
\draw[dashed] (12.5,0.5) -- (14.5,-0.5);
\draw[dashed] (12.5,-0.5) -- (14.5,-1.5);
\draw[dashed] (12.5,-1.5) -- (14.5,0.5);
\draw (12.5,1.5) -- (12,1) -- (12.5,0.5) -- (12,1) -- (11,0) -- (12,-1) -- (12.5,-0.5) -- (12,-1) -- (12.5,-1.5);
%\draw (14.5,1.5) -- (15.5,0.5) -- (15,0) -- (14.5,0.5) -- (15,0) -- (14.5,-0.5) -- (15.5,0.5) -- (16,0) -- (14.5,-1.5);
\draw (14.5,1.5) -- (16,0) -- (15.5,-0.5) -- (14.5,0.5) -- (15,0) -- (14.5,-0.5) -- (15,0) -- (15.5,-0.5) -- (14.5,-1.5);
\filldraw[fill=black,draw=black] (12,1) circle (1pt);
\filldraw[fill=black,draw=black] (11,0) circle (1pt);
\filldraw[fill=black,draw=black] (12,-1) circle (1pt);
\filldraw[fill=black,draw=black] (15,0) circle (1pt);
\filldraw[fill=black,draw=black] (15.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (16,0) circle (1pt);
\end{tikzpicture}
\end{center}
\caption{Layouts from Example \ref{layoutexample}.}
\vspace{-18pt}
\label{notation}
\end{figure}



\begin{comment}
\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.6]
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\draw[dashed] (-1,2) -- (1,-1);
\draw[dashed] (-1,1) -- (1,-2);
\draw[dashed] (-1,0) -- (1,1);
\draw[dashed] (-1,-1) -- (1,2);
\draw[dashed] (-1,-2) -- (1,0);
\draw (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-1.5,1.5) -- (-2,1) -- (-1,0) -- (-2,1) -- (-3,0) -- (-1,-2) -- (-1.5,-1.5) -- (-1,-1);
\draw (1,2) -- (2,1) --(1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0) -- (1.5,0.5) -- (2,1) -- (2.5,.5) -- (1,-1) -- (2.5,.5)-- (3,0) -- (1,-2);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,1) circle (1pt);
\filldraw[fill=black,draw=black] (-3,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (2,1) circle (1pt);
\filldraw[fill=black,draw=black] (3,0) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,0.5) circle (1pt);
\node at (-1,2.25) {$t_1$};
\node at (-1,1.25) {$t_2$};
\node at (-1,0.25) {$t_3$};
\node at (-1,-0.75) {$t_4$};
\node at (-1,-1.75) {$t_5$};
\node at (1,2.25) {$s_1$};
\node at (1,1.25) {$s_2$};
\node at (1,0.25) {$s_3$};
\node at (1,-0.75) {$s_4$};
\node at (1,-1.75) {$s_5$};

%%%%%%%%%%%%%%%%

\filldraw[fill=black,draw=black] (6,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (6,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (6,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (6,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (8,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (8,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (8,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (8,-1.5) circle (1pt);
\node at (6,1.75) {$t_1$};
\node at (6,0.75) {$t_2$};
\node at (6,-0.25) {$t_4$};
\node at (6,-1.25) {$t_5$};
\node at (8,1.75) {$s_1$};
\node at (8,0.75) {$s_3$};
\node at (8,-0.25) {$s_4$};
\node at (8,-1.25) {$s_5$};
\draw[dashed] (6,1.5) -- (8,-0.5);
\draw[dashed] (6,0.5) -- (8,-1.5);
\draw[dashed] (6,-0.5) -- (8,1.5);
\draw[dashed] (6,-1.5) -- (8,0.5);
\draw (6,1.5) -- (5.5,1) -- (6,0.5) -- (5.5,1) -- (4.5,0) -- (5.5,-1) -- (6,-0.5) -- (5.5,-1) -- (6,-1.5);
\draw (8,1.5) -- (8.5,1) -- (8,0.5) -- (8.5,1) -- (9,0.5) -- (8,-0.5) -- (9,0.5) -- (9.5,0) -- (8,-1.5);
\filldraw[fill=black,draw=black] (5.5,1) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0) circle (1pt);
\filldraw[fill=black,draw=black] (5.5,-1) circle (1pt);
\filldraw[fill=black,draw=black] (8.5,1) circle (1pt);
\filldraw[fill=black,draw=black] (9,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (9.5,0) circle (1pt);
\end{tikzpicture}
\caption{An induced subtanglegram on $\{1,2,4,5\}\subseteq [5]$.}
\label{subtanglegram}
\end{center}
\end{figure}
\end{comment}

%\textcolor{red}{********}fix the subtanglegram drawing here\textcolor{red}{********}

\section{Leaf-matched pairs and planar tanglegram layouts}\label{planar}

In this section, we discuss leaf-matched pairs, which allow us to characterize planar tanglegram layouts. We start with some definitions, followed by an example in Figure \ref{lmp}. We then give our \algname{ModifiedUntangle} algorithm. %For planar tanglegrams, this returns a planar layout $(X,Y)$ and the set of leaf-matched pairs $L$.

\begin{definition}
Let $(T,S,\phi)$ be a tanglegram with layout $(X,Y)$. A pair of internal vertices $(u,v)$ with $u\in T$ and $v\in S$ is a \textit{leaf-matched pair} of $(T,S,\phi)$ if $\leaf (u)$ and $\leaf(v)$ are matched by $\phi$. A \textit{paired flip} at $(u,v)$ is the operation on $(T,S,\phi)$ corresponding to a flip at $u$ and a flip at $v$. This maps $(X,Y)$ to the layout $(X',Y')$, where $X'$ is the image of $X$ after a flip at $u$ and $Y'$ is the image of $Y$ after a flip at $v$.
\end{definition}



\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.4]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed] (-1,2) -- (1,2);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) ; 
\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2,3) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (3.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\node at (-2.75,2.75) {\footnotesize{$u$}};
\node at (2.75,2.75) {\footnotesize{$v$}};
\node at (-0.8,4.375) {\footnotesize{$t_1$}};
\node at (-0.8,3.375) {\footnotesize{$t_2$}};
\node at (-0.8,2.375) {\footnotesize{$t_3$}};
\node at (-0.8,1.375) {\footnotesize{$t_4$}};
\node at (-0.8,0.375) {\footnotesize{$t_5$}};
\node at (-0.8,-0.625) {\footnotesize{$t_6$}};
\node at (-0.8,-1.625) {\footnotesize{$t_7$}};
\node at (-0.8,-2.625) {\footnotesize{$t_8$}};
\node at (0.8,4.375) {\footnotesize{$s_1$}};
\node at (0.8,3.375) {\footnotesize{$s_2$}};
\node at (0.8,2.375) {\footnotesize{$s_3$}};
\node at (0.8,1.375) {\footnotesize{$s_4$}};
\node at (0.8,0.375) {\footnotesize{$s_5$}};
\node at (0.8,-0.625) {\footnotesize{$s_6$}};
\node at (0.8,-1.625) {\footnotesize{$s_7$}};
\node at (0.8,-2.625) {\footnotesize{$s_8$}};
\filldraw[fill=black,draw=black] (1.5,-2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-2.5) circle (1pt);
\end{tikzpicture}
\quad
\begin{tikzpicture}[scale=0.4]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed] (-1,2) -- (1,2);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
\draw (1,1) -- (1.5,1.5) -- (1,2) -- (1.5,1.5) -- (2,2) -- (1,3) -- (2,2) -- (2.5,2.5) -- (1,4)  -- (4.5,0.5) ; 
\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2,2) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (3.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-2.5) circle (1pt);
\node at (-0.8,4.375) {\footnotesize{$t_4$}};
\node at (-0.8,3.375) {\footnotesize{$t_3$}};
\node at (-0.8,2.375) {\footnotesize{$t_2$}};
\node at (-0.8,1.375) {\footnotesize{$t_1$}};
\node at (-0.8,0.375) {\footnotesize{$t_5$}};
\node at (-0.8,-0.625) {\footnotesize{$t_6$}};
\node at (-0.8,-1.625) {\footnotesize{$t_7$}};
\node at (-0.8,-2.625) {\footnotesize{$t_8$}};
\node at (0.8,4.375) {\footnotesize{$s_4$}};
\node at (0.8,3.375) {\footnotesize{$s_3$}};
\node at (0.8,2.375) {\footnotesize{$s_2$}};
\node at (0.8,1.375) {\footnotesize{$s_1$}};
\node at (0.8,0.375) {\footnotesize{$s_5$}};
\node at (0.8,-0.625) {\footnotesize{$s_6$}};
\node at (0.8,-1.625) {\footnotesize{$s_7$}};
\node at (0.8,-2.625) {\footnotesize{$s_8$}};
\node at (-2.75,2.75) {\footnotesize{$u$}};
\node at (2.75,2.75) {\footnotesize{$v$}};
\end{tikzpicture}
\caption{Starting with the layout on the left, a paired flip at the leaf-matched pair $(u,v)$ results in the layout on the right.}\label{lmp}
\end{center}
\vspace{-24pt}
\end{figure}


\begin{algorithm}[H]\label{modifieduntangle}\DontPrintSemicolon
\caption{$\algname{ModifiedUntangle}$ (based on \cite[Algorithm 2]{layout})}
\KwIn{planar tanglegram $(T,S,\phi)$ with leaves $\{t_1,\ldots ,t_n\}$ and $\{s_1,\ldots ,s_n\}$}
\KwOut{a planar layout $(X,Y)$ of $(T,S,\phi)$, list of leaf-matched pairs $L\subseteq T\times S$}
$P\coloneqq$ Boolean table with $P[u,v]=False$ for all vertices $u\in T$, $v\in S$\label{booleantable}\\
set $P[t_i,s_{\phi(i)}]=True$ for all $i\in [n]$\\
recursively set $P[u,v]=True$ for internal vertices $u\in T,v\in S$ if there exists $u'\leq_T u$, $v'\leq_S v$ with $P[u',v']=True$\\
$X\coloneqq (\rut(T))$, $Y\coloneqq (\rut(S))$ as ordered lists\\
$E\coloneqq\{(\rut(T),\rut(S))\}$ as a set of edges\\
$L\coloneqq\emptyset$\\
\While{$X\cup Y$ contains an internal vertex of $T$ or $S$\label{partiallayouts}}
{$u\coloneqq$ an internal vertex of $T$ or $S$ with highest degree in the bipartite graph $G=(X,Y,E)$\label{highestdegree} \\
\If{$u\in X$} 
{
\If{$u$ has degree 1 in $G$} 
{update $L\coloneqq L\cup (u,v)$, where $v$ is the unique neighbor of $u$ in $G$}
update $X,E\coloneqq \algname{Refine}(X,Y,u,E,P)$ }
\ElseIf{$u\in Y$}
{
\If{$u$ has degree 1 in $G$} 
{update $L\coloneqq L\cup (v,u)$, where $v$ is the unique neighbor of $u$ in $G$}
update $Y,E\coloneqq \algname{Refine}(Y,X,u,E,P)$}
}
\Return $(X,Y),L$
\end{algorithm}


\begin{algorithm}[H]\DontPrintSemicolon
\caption{$\algname{Refine}$ (based on  \cite[Algorithm 3]{layout})}
\KwIn{ordered lists of vertices $(A,B)$, $u\in A$, edges $E$ on $A\cup B$, Boolean table $P$}
\KwOut{$A,E$ after $u$ has been replaced with its children}
$u_1,u_2\coloneqq$ children of $u$ in $T\cup S$\\
\ForEach{$j\in [m]$ such that $(u,b_j)\in E$ where $B=(b_1,\ldots ,b_m)$} 
{
update $E\coloneqq E\setminus \{(u,b_j)\}$ \tcp*{replace edges in $E$ involving $u$ with those involving $u_1,u_2$}
\ForEach{ $i\in \{1,2\}$ \label{edges}}
{
\If{$P[u_i,b_j]=True$}
{update $E\coloneqq E\cup \{(u_i,b_j)\}$}
}
}
$k\coloneqq \max\{j\in [m]:(u_1,b_j)\in E\}$ \tcp*{last vertex in $B$ adjacent to $u_1$}
\If {$j>k$ for all $(u_2,b_j)\in E$}
{
replace $u$ with $u_1u_2$ in $A$
}
\Else
{
replace $u$ with $u_2u_1$ in $A$
}
\Return $A,E$
\end{algorithm}



\begin{theorem}\cite{layout}\label{untangle}
For any planar tanglegram $(T,S,\phi)$ of size $n$, \algname{ModifiedUntangle} terminates in a planar layout $(X,Y)$ and runs in $O(n^2)$ time and space.
\end{theorem}


\begin{lemma}\label{degree1}
If $(T,S,\phi)$ is a planar tanglegram, then the set $L$ returned by \algname{ModifiedUntangle} is the set of leaf-matched pairs of $(T,S,\phi)$.
\end{lemma}

Using the techniques from the proof of Theorem \ref{untangle} and Lemma \ref{degree1}, we can establish Theorem \ref{planarlayouts}. Hence, we can use the output of \algname{ModifiedUntangle} to find all planar layouts of a tanglegram. Theorem \ref{planarlayouts} also gives us an interesting corollary about the flip graph of a planar tanglegram, which we now define. 


\begin{definition}
Let $(T,S,\phi)$ be a planar tanglegram. Define the \textit{flip graph of $(T,S,\phi)$} as $\Gamma(T,S,\phi)=(V,E)$ with vertices $v_{(X,Y)}\in V$ corresponding to planar layouts $(X,Y)$, and edges $(v_{(X,Y)},v_{(X',Y')})\in E$ if $(X',Y')$ can be obtained from $(X,Y)$ by a paired flip at some leaf-matched pair $(u,v)$ of $(T,S,\phi)$. 
\end{definition}

\begin{corollary}
The flip graph of a planar tanglegram is connected.
\end{corollary}

We can count the number of tanglegrams of size $n$ with $k$ leaf-matched pairs. Recall the generating functions $H(x)$ and $F(x,q)$ defined in (\ref{Hx}) and (\ref{Fxq}). Generalizing the arguments in \cite[Theorem 1]{countingplanar} establishes Theorem \ref{lmpcount}. Using this result, it takes a computer-algebra system a moment to generate several coefficients of $F(x,q)$. The coefficient of $x^nq^k$ counts the number of planar tanglegrams of size $n$ with $k$ leaf-matched pairs, and we collect these coefficients in Table \ref{leafmatchedtable}. See \cite[A349409]{oeis} for more terms. The corresponding planar tanglegrams for $n=4$ are shown in Figure \ref{size4tanglegrams}.

\begin{table}[h]
    \centering
    \begin{tabular}{c | c |  c | c| c| c |c |c |  c}
        $n,k$  & 1 &  2 & 3 & 4 & 5 & 6 & 7 & total \\  \hline 
        2 & 1 & & & & & & &  1\\  \hline 
        3 & 1 & 1 & & & & & & 2\\  \hline 
        4 & 5 & 4 & 2 & & & & & 11\\  \hline 
        5 & 34 & 28 & 11 & 3  & & & & 76\\  \hline 
        6 & 273 & 239 & 102 & 29 & 6 & & & 649\\  \hline 
        7 & 2436 & 2283 & 1045 & 325 & 73 & 11 & & 6173\\  \hline 
        8 & 23391 & 23475 & 11539 & 3852 & 968 & 181 & 23 & 63429\\  %\hline 
        %9 & 237090 & 254309 & 133690 & 47640 & 12923 & 2756 & 444 & 46 & 688898\\ 
    \end{tabular}
    \caption{The number of planar tanglegrams of size $n$ with $k$ leaf-matched pairs.}
    \label{leafmatchedtable}
\end{table}

\begin{figure}[h]
    \centering
    %1
    \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-1.5,1.5) -- (-1,1) -- (0,2) -- (-0.5,1.5) -- (0,1) -- (-0.5,1.5) -- (-1,1) -- (0,0);
    \draw (1,3) -- (1.5,2.5) -- (1,2) -- (1.5,2.5) -- (2.5,1.5) -- (1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \end{tikzpicture}
    \quad 
    %2
        \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-0.5,2.5) -- (0,2) -- (-0.5,2.5)-- (-1.5,1.5) -- (-0.5,0.5) -- (0,1) -- (-0.5,0.5) -- (0,0);
    \draw (1,3) -- (2.5,1.5) -- (2,1) -- (1,2) -- (1.5,1.5) -- (1,1) -- (1.5,1.5) -- (2,1) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \end{tikzpicture}
        \quad 
        %3
        \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-0.5,2.5) -- (0,2) -- (-0.5,2.5) -- (-1,2) -- (0,1) -- (-1,2) -- (-1.5,1.5) -- (0,0);
    \draw (1,3) -- (2.5,1.5) -- (2,1) -- (1,2) -- (2,1) -- (1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \end{tikzpicture}
            \quad 
            %4
        \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-1,2) -- (-0.5,1.5) -- (0,2) -- (-0.5,1.5) -- (0,1) -- (-1,2) -- (-1.5,1.5) -- (0,0);
    \draw (1,3) -- (2.5,1.5) -- (2,1) -- (1,2) -- (2,1) -- (1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \end{tikzpicture}
    \quad 
    %5
    \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-1.5,1.5) -- (-1,1) -- (0,2) -- (-1,1) -- (-0.5,0.5) -- (0,1) -- (-0.5,0.5) -- (0,0);
    \draw (1,3) -- (2,2) -- (1.5,1.5) -- (1,2) -- (1.5,1.5) -- (1,1) -- (2,2) -- (2.5,1.5) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \end{tikzpicture} \\
    \phantom{-}\\
    %6
    \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
        \draw (0,3) -- (-1.5,1.5) -- (-1,1) -- (0,2) -- (-1,1) -- (-0.5,0.5) -- (0,1) -- (-0.5,0.5) -- (0,0);
 \draw (1,3) -- (1.5,2.5) -- (1,2) -- (1.5,2.5) -- (2.5,1.5) -- (1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0);
 \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (1.5,0.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (-0.5,0.5) circle (1.5pt);
    \end{tikzpicture}
    \quad
    %7 
        \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-0.5,2.5) -- (0,2) -- (-0.5,2.5)-- (-1.5,1.5) -- (-0.5,0.5) -- (0,1) -- (-0.5,0.5) -- (0,0);
    \draw (1,3) -- (2.5,1.5) -- (2,1) -- (1,2) -- (2,1) -- (1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (1.5,0.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (-0.5,0.5) circle (1.5pt);
    \end{tikzpicture}
    %8
    \quad 
    \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-1,2) -- (-0.5,1.5) -- (0,2) -- (-0.5,1.5) -- (0,1) -- (-1,2) -- (-1.5,1.5) -- (0,0);
    \draw (1,3) -- (2.5,1.5) -- (2,1) -- (1,2) -- (1.5,1.5) -- (1,1) -- (1.5,1.5) -- (2,1) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (1.5,1.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (-0.5,1.5) circle (1.5pt);
    \end{tikzpicture}
    \quad 
    %9
    \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-1.5,1.5) -- (-1,1) -- (0,2) -- (-0.5,1.5) -- (0,1) -- (-0.5,1.5) -- (-1,1) -- (0,0);
   \draw (1,3) -- (2.5,1.5) -- (2,1) -- (1,2) -- (2,1) -- (1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0);
   \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (2,1) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (-1,1) circle (1.5pt);
    \end{tikzpicture}
    %\\
    %10
    \quad 
    %\phantom{-} \\
    \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
    \draw (0,3) -- (-0.5,2.5) -- (0,2) -- (-0.5,2.5)-- (-1.5,1.5) -- (-0.5,0.5) -- (0,1) -- (-0.5,0.5) -- (0,0);
    \draw (1,3) -- (1.5,2.5) -- (1,2) -- (1.5,2.5) -- (2.5,1.5) -- (1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (1.5,0.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (-0.5,0.5) circle (1.5pt);
    \filldraw[fill=blue,draw=blue] (1.5,2.5) circle (1.5pt);
    \filldraw[fill=blue,draw=blue] (-0.5,2.5) circle (1.5pt);
    \end{tikzpicture}
    \quad 
    %11
    \begin{tikzpicture}[scale=0.55]
    \filldraw[fill=black,draw=black] (0,3) circle (1pt);
    \filldraw[fill=black,draw=black] (0,2) circle (1pt);
    \filldraw[fill=black,draw=black] (0,1) circle (1pt);
    \filldraw[fill=black,draw=black] (0,0) circle (1pt);
    \filldraw[fill=black,draw=black] (1,3) circle (1pt);
    \filldraw[fill=black,draw=black] (1,2) circle (1pt);
    \filldraw[fill=black,draw=black] (1,1) circle (1pt);
    \filldraw[fill=black,draw=black] (1,0) circle (1pt);
    \draw[dashed] (0,3) -- (1,3);
    \draw[dashed] (0,2) -- (1,2);
    \draw[dashed] (0,1) -- (1,1);
    \draw[dashed] (0,0) -- (1,0);
        \draw (0,3) -- (-1.5,1.5) -- (-1,1) -- (0,2) -- (-1,1) -- (-0.5,0.5) -- (0,1) -- (-0.5,0.5) -- (0,0);
    \draw (1,3) -- (2.5,1.5) -- (2,1) -- (1,2) -- (2,1) -- (1.5,0.5) -- (1,1) -- (1.5,0.5) -- (1,0);
    \filldraw[fill=red,draw=red] (2.5,1.5) circle (1.5pt);
    \filldraw[fill=red,draw=red] (-1.5,1.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (1.5,0.5) circle (1.5pt);
    \filldraw[fill=green!75!black,draw=green!75!black] (-0.5,0.5) circle (1.5pt);
    \filldraw[fill=blue,draw=blue] (2,1) circle (1.5pt);
    \filldraw[fill=blue,draw=blue] (-1,1) circle (1.5pt);
    \end{tikzpicture}
    \caption{The 11 planar tanglegrams of size 4 with color-coded leaf-matched pairs. The first five tanglegrams have one leaf-matched pair, and hence are irreducible.  The following four have two pairs, and the final two have three pairs.}
    \label{size4tanglegrams}
    \vspace{-18pt}
\end{figure}

\section{The Tanglegram Single Edge Insertion Problem}\label{TEI}

In this section, we describe our \algname{Insertion} Algorithm for solving the Tanglegram Single Edge Insertion Problem. Throughout this section, fix a tanglegram $(T,S,\phi)$ of size $n$, fix $I=[n]\setminus \{i\}$ for some $i\in [n]$, and let $(X,Y)$ be a layout of $(T,S,\phi)$ that restricts to a planar layout of $(T_I,S_{\phi(I)},\phi|_I)$. We use the notation
\begin{equation}\label{operations}
\begin{split}
u_0&=\text{parent of $t_i\in T$}, \\
v_0&=\text{parent of $s_{\phi(i)}\in S$},\\
L(I)&=\{\text{leaf-matched pairs of $(T_I,S_{\phi(I)},\phi|_I)$}\},\\
L(I)_T&=\{(u,v)\in L(I):u>_T t_i,v\not>_S s_{\phi(i)}\},\\
L(I)_S&=\{(u,v)\in L(I):u\not>_T t_i,v>_S s_{\phi(i)}\}.
\end{split}
\end{equation}
An example of the sets $L(I)_T$ and $L(I)_S$ is given in Figure \ref{LITLIS}. Note that $u_0$ and $v_0$ are also the unique internal vertices in $(T,S,\phi)$ that are not in $(T_I,S_{\phi(I)},\phi|_I)$. Using these sets with our results from Section \ref{planar}, the Tanglegram Single Edge Insertion Problem reduces to certain operations at the elements above.

\begin{figure}
    \centering
    \begin{tikzpicture}[scale=0.55]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed] (-1,2) -- (1,2);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) ; 
\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2,3) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (3.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\node at (-2.875,2.75) {$u_3$};
\node at (2.875,2.75) {$v_3$};
\node at (-2,3.5) {$u_2$};
\node at (2,3.5) {$v_2$};
\node at (-1.875,-2.75) {$u_1$};
\node at (1.875,-2.75) {$v_1$};
\node[color=red] at (-1.625,4) {$u_0$};
\node[color=red] at (1.625,-2) {$v_0$};
\filldraw[fill=black,draw=black] (-2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\draw[color=red] (-1.25,3.75) -- (-1,3.5) -- (1,-2.5) -- (1.25,-2.25);
\filldraw[fill=red,draw=red] (-1.25,3.75) circle (1pt);
\filldraw[fill=red,draw=red] (-1,3.5) circle (1pt);
\filldraw[fill=red,draw=red] (1,-2.5) circle (1pt);
\filldraw[fill=red,draw=red] (1.25,-2.25) circle (1pt);
\node[color=red] at (-.625,3.5) {$t_i$};
\node[color=red] at (.25,-2.5) {$s_{\phi(i)}$};
\filldraw[fill=black,draw=black] (1.5,-2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-2.5) circle (1pt);
%\draw (-1.2,2.2)--(1.2,2.2) -- (1.2,0.8) -- (-1.2,0.8) -- (-1.2,2.2);
%\node at (0,2.55) {\small{$E(u_3,v_3)$}};
%\node[color=white] at (0,-3.6) {\small{$E(v_1)$}};
\end{tikzpicture}
    \caption{For the tanglegram given above with subtanglegram $(T_I,S_{\phi(I)},\phi|_I)$ shown in black, $L(I)_T=\{(u_2,v_2),(u_3,v_3)\}$ and $L(I)_S=\{(u_1,v_1)\}$. Note that $(\rut(T),\rut(S))\in L(I)$ is not an element of either set since $\rut(T)>_T t_i$ and $\rut(S)>_S s_{\phi(i)}$.}
    \label{LITLIS}
    \vspace{-18pt}
\end{figure}

\newpage 
\begin{definition}
Let $T$ be a tree, let $u\in T$ be an internal vertex, and let $u_1,u_2$ be the children of $u$. A \textit{subtree switch} at $u$ is the operation on $T$ that interchanges the two subtrees rooted at $u_1$ and $u_2$, while maintaining the relative order of all leaves within each subtree. 
%Note that a subtree switch is equivalent to a flip at $u$ and then a flip at each child of $u$ that is not a leaf.
\end{definition}

Observe that a subtree switch at $u$ is equivalent to a flip at $u$ and a flip at each of its children. On a layout $(X,Y)$ of a tanglegram $(T,S,\phi)$, the action of a subtree switch at $u$ interchanges the order of the two sublists corresponding to $\leaf(u_1)$ and $\leaf(u_2)$.

\begin{lemma}\label{existence}
A solution to the Tanglegram Single Edge Insertion Problem can be obtained by starting at $(X,Y)$ and performing a sequence of paired flips at $(u,v)\in L(I)_T\cup L(I)_S$ and subtree switches at $u_0$ and $v_0$.
\end{lemma}

Identifying a solution in Lemma \ref{existence} will require some cases. Notice that $u>_T u_0$ for any $(u,v)\in L(I)_T$ and $v>_S v_0$ for any $(u,v)\in L(I)_S$, as $u_0$ and $v_0$ are respectively the parents of $t_i$ and $s_{\phi(i)}$. Additionally, whenever $L(I)_T$ and $L(I)_S$ are nonempty, each set has a unique ``maximal'' element, which we denote
\begin{equation}\label{TmaxSmax}
\begin{split}
(u_{\mathrm{Tmax}},v_{\mathrm{Tmax}})&=\text{unique $(u,v)\in L(I)_T$ such that $u\geq_T u'$ for all $(u',v')\in L(I)_T$},\\
(u_{\mathrm{Smax}},v_{\mathrm{Smax}})&=\text{unique $(u,v)\in L(I)_S$ such that $v\geq_S v'$ for all $(u',v')\in L(I)_S$}.
\end{split}
\end{equation}
%Relations between $u_\mathrm{Smax}$ and $u_0$ or $v_\mathrm{Tmax}$ and $v_0$. 

\begin{lemma}
If $L(I)_S\neq \emptyset$ and $u_0>_T u_{\mathrm{Smax}}$, then $L(I)_T=\emptyset$. If $L(I)_T\neq \emptyset$ and $v_0>_S v_\mathrm{Tmax}$, then $L(I)_S=\emptyset$.
\end{lemma} 

When $u_0>_T u_{\mathrm{Smax}}$, the previous lemma implies $L(I)_T=\emptyset$. In this case, we find a solution in Lemma \ref{existence} by considering operations at $u_0, (u,v)\in L(I)_S$, and $v_0$ in the unique order such that no element is considered before all of its ancestors have been considered. We make paired flip and subtree switch choices greedily based on the crossings that can be affected by operations at the given vertices, but not by operations we consider afterwards. An example is shown in Figure \ref{insertioncase1ex}. The case $v_0>_S v_{\mathrm{Tmax}}$ is similar.
%between-tree edges sets that we call $E(u_0)$, $E(v_0)$, and $E(u,v)$ for $(u,v)\in L(I)_S$. These sets track crossings that can be affected by operations at the given vertices, but not at any descendants. An example is shown in Figure \ref{insertioncase1ex}. Our algorithm for the case $v_0>_S v_\mathrm{Tmax}$ is similar.




\begin{figure}[h]
\begin{center}
    \begin{tikzpicture}[scale=0.55]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed,line width=0.5mm,color=green!75!black] (-1,2) -- (1,2);
\draw[dashed,line width=0.5mm,color=green!75!black] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5)-- (-1,3) -- (-1.5,3.5) -- (-4.5,0.5) -- (-3.5,-0.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-1.5,1.5) -- (-3.5,-0.5) -- (-2.5,-1.5) -- (-1,0) -- (-2,-1) -- (-1.5,-1.5) -- (-1,-1) -- (-1.5,-1.5) -- (-1,-2) -- (-2,-1) -- (-2.5,-1.5) -- (-1,-3);
\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) -- (2.5,-1.5) -- (1,0) -- (2.5,-1.5) -- (1,-3) -- (2,-2) -- (1,-1) -- (1.5,-1.5) -- (1,-2);
%\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
%\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
%\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) ; 
%\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
%\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-1) circle (1pt);
\filldraw[fill=black,draw=black] (2,3) circle (1pt);
\filldraw[fill=black,draw=black] (2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-1) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-3.5,-0.5) circle (1pt);
\draw[color=red] (-3.75,-0.25) -- (-1,2.5) -- (1,-0.5) -- (1.25,-1.25);
\filldraw[fill=red,draw=red] (-3.75,-0.25) circle (1pt);
\filldraw[fill=red,draw=red] (-1,2.5) circle (1pt);
\filldraw[fill=red,draw=red] (1,-0.5) circle (1pt);
\filldraw[fill=red,draw=red] (1.25,-1.25) circle (1pt);
\node[color=red] at (-0.5,2.625) {\small{$t_i$}};
\node[color=red] at (0.25,-0.5) {\small{$s_{\phi(i)}$}};
\filldraw[fill=black,draw=black] (1.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-1.5) circle (1pt);
\node[color=white] at (-0.5,-3.625) {\small{$t_i$}};
\node[color=red] at (-4,-0.5) {\small{$u_0$}};
\node[color=red] at (1.5,-1) {\small{$v_0$}};
\node at (-1.875,-1.5) {\small{$u_1$}};
\node at (1.875,-1.5) {\small{$v_1$}};
\node at (-3,-1.5) {\small{$u_2$}};
\node at (3,-1.5) {\small{$v_2$}};
%\draw (1.2,2.2) -- (-1.2,2.2) -- (-1.2,0.8) -- (1.2,0.8) -- (1.2,2.2);
%\node at (0,1.5) {\small{$E(u_0)$}};
\end{tikzpicture}
\phantom{-}
\begin{tikzpicture}[scale=0.55]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed] (-1,2) -- (1,2);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed,line width=0.5mm,color=green!75!black] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed,line width=0.5mm,color=green!75!black] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5)-- (-1,3) -- (-1.5,3.5) -- (-4.5,0.5) -- (-3.5,-0.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-1.5,1.5) -- (-3.5,-0.5) -- (-2.5,-1.5) -- (-1,0) -- (-2,-1) -- (-1.5,-1.5) -- (-1,-1) -- (-1.5,-1.5) -- (-1,-2) -- (-2,-1) -- (-2.5,-1.5) -- (-1,-3);
\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) -- (2.5,-1.5) -- (1,0) -- (2.5,-1.5) -- (1,-3) -- (2,-2) -- (1,-1) -- (1.5,-1.5) -- (1,-2);
%\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
%\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
%\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) ; 
%\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
%\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-1) circle (1pt);
\filldraw[fill=black,draw=black] (2,3) circle (1pt);
\filldraw[fill=black,draw=black] (2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-1) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-3.5,-0.5) circle (1pt);
\draw[color=red] (-3.75,-0.25) -- (-1,-3.5) -- (1,-0.5) -- (1.25,-1.25);
\filldraw[fill=red,draw=red] (-3.75,-0.25) circle (1pt);
\filldraw[fill=red,draw=red] (-1,-3.5) circle (1pt);
\filldraw[fill=red,draw=red] (1,-0.5) circle (1pt);
\filldraw[fill=red,draw=red] (1.25,-1.25) circle (1pt);
\node[color=red]  at (-0.5,-3.625) {\small{$t_i$}};
\node[color=red] at (0.125,-0.625) {\small{$s_{\phi(i)}$}};
\filldraw[fill=black,draw=black] (1.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-1.5) circle (1pt);
%\node[color=white] at (1,-3.625) {$\leaf'(v_1)$};
\node[color=red] at (-4,-0.5) {\small{$u_0$}};
\node[color=red] at (1.5,-1) {\small{$v_0$}};
\node at (-1.875,-1.5) {\small{$u_1$}};
\node at (1.875,-1.5) {\small{$v_1$}};
\node at (-3,-1.5) {\small{$u_2$}};
\node at (3,-1.5) {\small{$v_2$}};
%\draw (1.2,2.2) -- (-1.2,2.2) -- (-1.2,0.8) -- (1.2,0.8) -- (1.2,2.2);
%\node at (0,0.55) {\small{$E(u_2,v_2)$}};
%\node at (0,-2.5) {\small{$E(v_2)$}};
%\draw (1.2,0.2) -- (-1.2,0.2) -- (-1.2,-0.2) -- (1.2,-0.2) -- (1.2,0.2);
%\draw (1.2,-2.8) -- (-1.2,-2.8) -- (-1.2,-3.2) -- (1.2,-3.2) -- (1.2,-2.8);
\end{tikzpicture}
\phantom{-}
\begin{tikzpicture}[scale=0.55]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed] (-1,2) -- (1,2);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5)-- (-1,3) -- (-1.5,3.5) -- (-4.5,0.5) -- (-3.5,-0.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-1.5,1.5) -- (-3.5,-0.5) -- (-2.5,-1.5) -- (-1,0) -- (-2,-1) -- (-1.5,-1.5) -- (-1,-1) -- (-1.5,-1.5) -- (-1,-2) -- (-2,-1) -- (-2.5,-1.5) -- (-1,-3);
\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) -- (2.5,-1.5) -- (1,0) -- (2.5,-1.5) -- (1,-3) -- (2,-2) -- (1,-1) -- (1.5,-1.5) -- (1,-2);
%\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
%\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
%\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) ; 
%\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
%\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-1) circle (1pt);
\filldraw[fill=black,draw=black] (2,3) circle (1pt);
\filldraw[fill=black,draw=black] (2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-1) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-3.5,-0.5) circle (1pt);
\draw[color=red] (-3.75,-0.25) -- (-1,-3.5) -- (1,-2.5) -- (1.25,-1.75);
\filldraw[fill=red,draw=red] (-3.75,-0.25) circle (1pt);
\filldraw[fill=red,draw=red] (-1,-3.5) circle (1pt);
\filldraw[fill=red,draw=red] (1,-2.5) circle (1pt);
\filldraw[fill=red,draw=red] (1.25,-1.75) circle (1pt);
\node[color=red] at (-0.5,-3.625) {\small{$t_i$}};
\node[color=red] at (0.25,-2.375) {\small{$s_{\phi(i)}$}};
\filldraw[fill=black,draw=black] (1.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-1.5) circle (1pt);
%\node[color=white] at (1,-3.625) {$\leaf'(v_1)$};
\node[color=red] at (-4,-0.5) {\small{$u_0$}};
\node[color=red] at (1.5,-2.125) {\small{$v_0$}};
\node at (-1.875,-1.5) {\small{$u_1$}};
\node at (1.875,-1.5) {\small{$v_1$}};
\node at (-3,-1.5) {\small{$u_2$}};
\node at (3,-1.5) {\small{$v_2$}};
\end{tikzpicture}
\caption{In this example, $L(I)_S=\{(u_1,v_1),(u_2,v_2)\}$ with $(u_{\mathrm{Smax}},v_{\mathrm{Smax}})=(u_2,v_2)$. Starting with $(X,Y)$ on the left, a subtree switch at $u_0$ determines whether $(t_i,s_{\phi(i)})$ crosses the edges in green. Performing a subtree switch at $u_0$ removes these crossings, resulting in the middle layout. Subsequent steps include no operation at $(u_2,v_2)$, a paired flip at 
$(u_1,v_1)$, and no operation at $v_0$, returning the layout on the right.}
%perform a subtree switch at $u_0$ to obtain the layout in the middle. After not performing a paired flip at $(u_2,v_2)$, performing a paired flip at $(u_1,v_1)$, and not performing a subtree switch at $v_0$, it will return the layout on the right with one crossing.}
\label{insertioncase1ex}
\vspace{-24pt}
\end{center}
\end{figure}


 For all remaining cases, we first consider the elements of $L(I)_T$ in descending order with respect to ancestry, followed by the elements of $L(I)_S$ in descending order. We again make paired flip choices greedily based on crossings that cannot be affected by operations we consider afterwards. We then consider the four layouts generated by all combinations of subtree switches at $u_0$ and $v_0$, and we return the layout with the fewest number of crossings. An example of this procedure is shown in Figure \ref{insertion-ex}.


\begin{figure}[h]
\begin{center}
\begin{tikzpicture}[scale=0.55]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed,line width=0.5mm,color=green!75!black] (-1,2) -- (1,2);
\draw[dashed,line width=0.5mm,color=green!75!black] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
\draw (1,4) -- (1.5,3.5) -- (1,3) -- (1.5,3.5) -- (2,3) -- (1,2) -- (2,3) -- (2.5,2.5) -- (1,1) -- (2.5,2.5) -- (4.5,0.5) ; 
\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2,3) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (3.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\node at (-2.875,2.75) {$u_3$};
\node at (2.875,2.75) {$v_3$};
\node at (-2,3.5) {$u_2$};
\node at (2,3.5) {$v_2$};
\node at (-1.875,-2.75) {$u_1$};
\node at (1.875,-2.75) {$v_1$};
\node[color=red] at (-1.625,4) {$u_0$};
\node[color=red] at (1.625,-2) {$v_0$};
\filldraw[fill=black,draw=black] (-2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\draw[color=red] (-1.25,3.75) -- (-1,3.5) -- (1,-2.5) -- (1.25,-2.25);
\filldraw[fill=red,draw=red] (-1.25,3.75) circle (1pt);
\filldraw[fill=red,draw=red] (-1,3.5) circle (1pt);
\filldraw[fill=red,draw=red] (1,-2.5) circle (1pt);
\filldraw[fill=red,draw=red] (1.25,-2.25) circle (1pt);
\node[color=red] at (-.625,3.5) {$t_i$};
\node[color=red] at (.375,-2.5) {$s_{\phi(i)}$};
\filldraw[fill=black,draw=black] (1.5,-2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-2.5) circle (1pt);
%\draw (-1.2,2.2)--(1.2,2.2) -- (1.2,0.8) -- (-1.2,0.8) -- (-1.2,2.2);
%\node at (0,2.55) {\small{$E(u_3,v_3)$}};
%\node[color=white] at (0,-3.6) {\small{$E(v_1)$}};
\end{tikzpicture}
\phantom{-}
\begin{tikzpicture}[scale=0.55]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed,line width=0.5mm,color=green!75!black] (-1,2) -- (1,2);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed,line width=0.5mm,color=blue] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
\draw (1,1) -- (1.5,1.5) -- (1,2) -- (1.5,1.5) -- (2,2) -- (1,3) -- (2,2) -- (2.5,2.5) -- (1,4)  -- (4.5,0.5) ; 
\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2,2) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (3.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-2.5) circle (1pt);
\node at (-2.875,2.75) {$u_3$};
\node at (2.875,2.75) {$v_3$};
\node at (-2,1.5) {$u_2$};
\node at (2,1.5) {$v_2$};
\node at (-1.875,-2.75) {$u_1$};
\node at (1.75,-2.75) {$v_1$};
\node[color=red] at (-1.5,1) {$u_0$};
\node[color=red] at (1.5,-2) {$v_0$};
\draw[color=red] (-1.25,1.25) -- (-1,1.5) -- (1,-2.5) -- (1.25,-2.25);
\filldraw[fill=red,draw=red] (-1.25,1.25) circle (1pt);
\filldraw[fill=red,draw=red] (-1,1.5) circle (1pt);
\filldraw[fill=red,draw=red] (1,-2.5) circle (1pt);
\filldraw[fill=red,draw=red] (1.25,-2.25) circle (1pt);
\node[color=red] at (-.625,1.5) {$t_i$};
\node[color=red] at (.25,-2.5) {$s_{\phi(i)}$};
%\draw (-1.2,2.2) -- (1.2,2.2) -- (1.2,1.8) -- (-1.2,1.8) -- (-1.2,2.2);
%\node at (0,2.55) {\small{$E(u_2,v_2)$}};
%\draw (-1.2,-3.2) -- (1.2,-3.2) -- (1.2,-2.8) -- (-1.2,-2.8) -- (-1.2,-3.2);
%\node at (0,-3.6) {\small{$E(u_1,v_1)$}};
\end{tikzpicture}
\phantom{-}
\begin{tikzpicture}[scale=0.55]
\filldraw[fill=black,draw=black] (1,4) circle (1pt);
\filldraw[fill=black,draw=black] (1,3) circle (1pt);
\filldraw[fill=black,draw=black] (1,2) circle (1pt);
\filldraw[fill=black,draw=black] (1,1) circle (1pt);
\filldraw[fill=black,draw=black] (1,0) circle (1pt);
\filldraw[fill=black,draw=black] (1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (1,-3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,4) circle (1pt);
\filldraw[fill=black,draw=black] (-1,3) circle (1pt);
\filldraw[fill=black,draw=black] (-1,2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,0) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-1) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-2) circle (1pt);
\filldraw[fill=black,draw=black] (-1,-3) circle (1pt);
\draw[dashed] (-1,4) -- (1,4);
\draw[dashed] (-1,3) -- (1,3);
\draw[dashed] (-1,2) -- (1,2);
\draw[dashed] (-1,1) -- (1,1);
\draw[dashed] (-1,0) -- (1,0);
\draw[dashed] (-1,-1) -- (1,-1);
\draw[dashed] (-1,-2) -- (1,-2);
\draw[dashed] (-1,-3) -- (1,-3);
\draw (-1,4) -- (-1.5,3.5) -- (-1,3) -- (-1.5,3.5) -- (-2.5,2.5) -- (-1.5,1.5) -- (-1,2) -- (-1.5,1.5) -- (-1,1) -- (-2.5,2.5) -- (-4.5,0.5);
\draw (-1,-3) -- (-1.5,-2.5) -- (-1,-2) -- (-1.5,-2.5) -- (-2,-2) -- (-1,-1) -- (-2,-2) -- (-2.5,-1.5) -- (-1,0) -- (-2.5,-1.5) -- (-4.5,0.5);
\draw (1,1) -- (1.5,1.5) -- (1,2) -- (1.5,1.5) -- (2,2) -- (1,3) -- (2,2) -- (2.5,2.5) -- (1,4)  -- (4.5,0.5) ; 
\draw (1,-3) -- (1.5,-2.5) -- (1,-2) -- (1.5,-2.5) -- (4.5,0.5);
\draw (1,0) -- (1.5,-0.5) -- (1,-1) -- (1.5,-0.5) --(3.5,1.5);
\filldraw[fill=black,draw=black] (-1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,-1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2,-2) circle (1pt);
\filldraw[fill=black,draw=black] (2,2) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-0.5) circle (1pt);
\filldraw[fill=black,draw=black] (3.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,3.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,1.5) circle (1pt);
\filldraw[fill=black,draw=black] (2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-2.5,2.5) circle (1pt);
\filldraw[fill=black,draw=black] (4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (-4.5,0.5) circle (1pt);
\filldraw[fill=black,draw=black] (1.5,-2.5) circle (1pt);
\filldraw[fill=black,draw=black] (-1.5,-2.5) circle (1pt);
\node at (-2.875,2.75) {$u_3$};
\node at (2.875,2.75) {$v_3$};
\node at (-2,1.5) {$u_2$};
\node at (2,1.5) {$v_2$};
\node at (-1.875,-2.75) {$u_1$};
\node at (1.75,-2.75) {$v_1$};
\node[color=red] at (-1.5,1) {$u_0$};
\node[color=red] at (1.5,-2) {$v_0$};
\draw[color=red] (-1.25,1.25) -- (-1,0.5) -- (1,-1.5) -- (1.25,-2.25);
\filldraw[fill=red,draw=red] (-1.25,1.25) circle (1pt);
\filldraw[fill=red,draw=red] (-1,0.5) circle (1pt);
\filldraw[fill=red,draw=red] (1,-1.5) circle (1pt);
\filldraw[fill=red,draw=red] (1.25,-2.25) circle (1pt);
\node[color=red] at (-.625,0.5) {$t_i$};
\node[color=red] at (.25,-1.5) {$s_{\phi(i)}$};
%\node[color=white] at (0,-3.6) {\small{$E(u_1,v_1)$}};
\end{tikzpicture}
\caption{Starting with $(X,Y)$ on the left, we perform a paired flip at $(u_3,v_3)$ to minimize crossings between $(t_i,s_{\phi(i)})$ and the edges in green, obtaining the layout in the middle. For $(u_2,v_2)$ and $(u_1,v_1)$, we respectively consider the edges shown in green and blue, and ultimately do not perform either of those paired flips. After considering all choices of subtree switches at $u_0$ and $v_0$, we return the layout shown on the right.}
\label{insertion-ex}
\vspace{-24pt}
\end{center}
\end{figure}



For our \algname{Insertion} Algorithm, first use \algname{ModifiedUntangle} on $(T,S,\phi|_I)$ to find a layout $(X,Y)$ of $(T,S,\phi)$ that restricts to a planar layout of $(T_I,S_{\phi(I)},\phi|_I)$. Then construct $L(I)_T$ and $L(I)_S$. Afterwards, check for the different cases involving $u_{\mathrm{Smax}}$ or $v_{\mathrm{Tmax}}$, and proceed accordingly. After formalizing this procedure, we obtain Theorem \ref{insertiontheorem}.

\begin{comment}
\begin{theorem}\label{insertiontime}
The \algname{Insertion} Algorithm solves the Tanglegram Single Edge Insertion Problem in $O(n^2)$ time and space, where $n$ is the size of the tanglegram.
\end{theorem}
\end{comment}

\section{Future Work}

In Section \ref{planar}, we defined the flip graph of a planar tanglegram. While paired flips will generate all vertices in this graph, it is possible that some flips do not produce a new layout, as tanglegrams are considered up to isomorphism on $T$ and $S$. One simple example of this is the unique tanglegram of size $2$, where a paired flip at the roots of both trees does not produce a new layout. As such, we pose the following problem.

\begin{problem}
For any planar tanglegram $(T,S,\phi)$, characterize the flip graph $\Gamma(T,S,\phi)=(V,E)$. In particular, determine  $|V|$, $|E|$, and $\deg(v)$ for $v\in V$.%, the number of edges, and the degree of any vertex.
\end{problem}

Our next problem involves generating tanglegrams uniformly at random. Billey, Konvalinka, and Matsen previously constructed an algorithm that generates tanglegrams uniformly at random in \cite{count}, and we propose a corresponding problem for the planar case. %Ralaivaosaona, Ravelomanana, and Wagner gave a bijection between irreducible planar tanglegrams and pairs of disjoint triangulations of a polygon in \cite{countingplanar}, so solving this problem may also lead to an algorithm for generating a pair of disjoint triangulations uniformly at random.

\begin{problem}
Find an efficient algorithm for generating a planar tanglegram of size $n$ uniformly at random.
\end{problem}

Finally, one can find examples where a solution to the Tanglegram Single Edge Insertion Problem is not a solution to the Tanglegram Layout Problem, such as the ones constructed in \cite[Corollary 4.18]{liu2022}. However, we could consider flips that do not preserve planarity of the subtanglegram but do reduce the number of crossings.

\begin{problem}
Can the \textit{Insertion} algorithm be modified to create an efficient approximation algorithm for the crossing number of an almost planar tanglegram?
\end{problem}

\acknowledgements{
We would like to thank Sara Billey for suggesting tanglegrams as an area of research and for valuable feedback. We would also like to thank Matja\v{z} Konvalinka, Stark Ryan, and the anonymous reviewers for valuable feedback on earlier versions of this paper.
}


\printbibliography

\end{document}
