\documentclass[12pt]{article}
\usepackage{e-jc}

% Packages
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc}
\usepackage{amsfonts,amsmath}
\usepackage[shortlabels]{enumitem}
\usepackage{graphicx}
\usepackage[svgnames]{xcolor}
\usepackage{tikz}
\usepackage{url}
\usepackage{hyperref}
\usepackage[pagewise]{lineno}
\usepackage{setspace}
\usepackage{algorithm}
\usepackage{algorithmicx}
\usepackage{algpseudocode}
\algnewcommand\algorithmicinput{\textbf{Input:}}
\algnewcommand\Input{\item[\algorithmicinput]}
\algnewcommand\algorithmicoutput{\textbf{Output:}}
\algnewcommand\Output{\item[\algorithmicoutput]}

% Macros
\newcommand{\crt}{\operatorname{crt}}
\newcommand{\cL}{\mathcal{L}}
\newcommand{\cT}{\mathcal{T}}
\newcommand{\cA}{\mathcal{A}}
\newcommand{\cD}{\mathcal{D}}
\newcommand{\red}{\color{red}}

\makeatletter
\let\@fnsymbol\@arabic
\makeatother

\begin{document}

\dateline{September 23, 2017}{October 5, 2018}{TBD}
\MSC{05C10, 05C62, 05C05,92B10}
\Copyright{  The authors. Released under the CC BY license (International 4.0).}
\title{Analogies between the Crossing Number\\ and the Tangle Crossing Number}

\author{Robin Anderson\footnotemark[1] \quad
Shuliang Bai\footnotemark[2] \quad
Fidel Barrera-Cruz\footnotemark[3] \quad
\'Eva Czabarka\footnotemark[2] \textsuperscript{,}\footnotemark[9]  \\
Giordano Da Lozzo\footnotemark[4] \quad
Natalie L. F. Hobson\footnotemark[5] \quad
Jephian C.-H. Lin\footnotemark[6] \\
Austin Mohr\footnotemark[7] \quad
Heather C. Smith\footnotemark[8]  \quad
L\'aszl\'o A. Sz\'ekely\footnotemark[2] \textsuperscript{,}\footnotemark[9]  \quad
Hays Whitlatch\footnotemark[2]  }

\maketitle

\footnotetext[1]{Department of Mathematics, Saint Louis University, St. Louis, MO, U.S.A. (\texttt{rander43@slu.edu}).}

\footnotetext[2]{Department of Mathematics, University of South Carolina, Columbia, SC, U.S.A. (\texttt{\{sbai,czabarka,szekely,hww\}@math.sc.edu}).}

\footnotetext[3]{ Sunnyvale, CA, U.S.A. (\texttt{fidel.barrera@gmail.com}).}

\footnotetext[4]{Department of Computer Science, Roma Tre University, Rome, Italy (\texttt{dalozzo@dia.uniroma3.it}).}

\footnotetext[5]{Department of Mathematics \& Statistics, Sonoma State University, Rohnert Park, CA,  
U.S.A. (\texttt{hobsonn@sonoma.edu}).}

\footnotetext[6]{Department of Mathematics,  Iowa State University,  Ames, IA, U.S.A. (\texttt{jephianlin@gmail.com}).}

\footnotetext[7]{Department of Mathematics,  Nebraska Wesleyan University, Lincoln, NE, U.S.A. (\texttt{amohr@nebrwesleyan.edu}).}

\footnotetext[8]{Dept. of Mathematics \& Computer Science,  Davidson College, Davidson, NC, U.S.A. (\texttt{hcsmith@davidson.edu}). Much of Smith's research was completed while affiliated with the Georgia Institute of Technology, Atlanta, GA, U.S.A.}

\footnotetext[9]{Czabarka and Sz\'ekely are also  Visiting Professors in the  Department of Pure and Applied Mathematics, University of Johannesburg, Johannesburg 2006, South Africa}


\begin{abstract}
Tanglegrams are special graphs that consist of a pair of rooted binary trees with the same number of leaves, and a perfect matching between the
two leaf-sets. These objects are of use in phylogenetics and are represented with straight-line drawings where the leaves of the two plane binary trees are on two parallel lines and only the matching edges can cross. The tangle crossing number of a tanglegram is the minimum number of crossings over all such drawings and is related to biologically relevant quantities, such as the number of times a parasite switched hosts.

Our main results for tanglegrams which parallel known theorems for crossing numbers are as follows.
The removal of a single matching edge in a tanglegram with $n$ leaves decreases the tangle crossing number by at most $n-3$, and this is sharp.
Additionally, if $\gamma(n)$ is the maximum
tangle crossing number of a tanglegram with $n$ leaves, we prove
$\frac{1}{2}\binom{n}{2}(1-o(1))\le\gamma(n)<\frac{1}{2}\binom{n}{2}$.
For an arbitrary tanglegram $T$, the tangle crossing number, $\crt(T)$, is NP-hard to compute (Fernau et al.\ 2005). We provide an algorithm which lower bounds $\crt(T)$ and runs in $O(n^4)$ time. To demonstrate the strength of the algorithm, simulations on tanglegrams chosen uniformly at random suggest that the tangle crossing number is at least $0.055n^2$ with high probabilty, which matches the result that the tangle crossing number is $\Theta(n^2)$ with high probability (\mbox{Czabarka} et al.\ 2017).
\end{abstract}




\section{Introduction}
\label{sec:intro}
A drawing $\cD(G)$ of a graph $G$ in the plane is a set of distinct points in the plane,
one for each vertex of $G$, and a collection of simple open arcs, one for each
edge of the graph, such that if $e$ is an edge of $G$ with endpoints $v$ and $w$, then the
closure (in the plane) of the arc $\alpha$ representing $e$ consists precisely of $\alpha$ and
the two points representing $v$ and $w$. We further require that no edge--arc
intersects any vertex point. The (standard) crossing number $\operatorname{cr}(\cD(G))$ of $\cD(G)$ is the number of
pairs $(x, \{\alpha,\beta\})$, where $x$ is a point of the plane, $\alpha,\beta$ are arcs of $\cD$
representing distinct edges of $G$ such that $x\in\alpha\cap\beta$.
The crossing number $\operatorname{cr}(G)$ of a graph $G$ is defined
to be the minimum crossing number over all of its drawings.

Tanglegrams are
well studied in the phylogenetics and computer science literature~\cite{BT, FKP, HN}. A
tanglegram of size $n$ is a triplet containing two rooted binary trees ($L$ and $R$), each
with $n$ leaves, and a fixed perfect matching $M$ between the two sets of leaves.
Two tanglegrams $T_1=(L_1,R_1,M_1)$ and $T_2=(L_2,R_2,M_2)$ are the same
if there is a pair of tree-isomorphisms $(\phi,\psi)$ from $L_1$ to $L_2$ and from $R_1$ to $R_2$ that
map each pair of matched leaves to a pair of matched leaves.
A layout of a
tanglegram is a straight-line plane drawing of the trees, the first
drawn in the half plane $x\leq 0$ with its leaves on the line $x=0$
and the second in the half plane $x\geq 1$ with its leaves on the line
$x=1$, with a straight-line drawing of the matching edges between the
leaves.  The tangle crossing number $\crt(T)$ of a tanglegram $T$ is the minimum crossing number over all
of its layouts, i.e., the minimum number of unordered pairs of
crossing edges over all layouts. The tangle crossing number
is related to the number of
times parasites switch hosts~\cite{HN} as well as the number of
horizontal gene transfers~\cite{BT}.

Though tangle crossing numbers are crossing numbers of a very specific kind of drawing of a very specific class of graphs,
a number of analogies are known between tangle crossing numbers and crossing numbers.
As with the crossing numbers of general graphs~\cite{GJ}, computing the tangle
crossing number is NP-hard~\cite{FKP}, even when both trees are
complete binary trees~\cite{BBBN}.
Testing whether a graph is planar can be done in polynomial (in fact linear) time~\cite{HT74}. Analogously, testing for tangle crossing number 0 can also be done in linear time~\cite{FKP}. Recently, Czabarka, Sz\'ekely, and
Wagner~\cite{CSW2} gave an analogue of Kuratowski's Theorem~\cite{Kura} for tanglegrams, characterizing tangle crossing number 0.
Clearly, for a graph $G$ with $e$ edges we have $\operatorname{cr}(G)=O(e^2)$, while for a tanglegram $T$ of size $n$,
$\crt(T)=O(n^2)$.
The expected crossing number of an Erd\H{o}s--R\'enyi random graph $G\in G(n,p)$ for $p=\frac{c}{n}$ for any $c>1$
is $\Theta(e^2)$ where $e=p\binom{n}{2}$ is the expected number of edges~\cite{SpT},
and the expected tangle crossing number of a random and uniformly
selected tanglegram with $n$ leaves is $\Theta(n^2)$~\cite{CSW}, i.e., both of these quantities are as large as possible in order of
magnitude.

We continue the study of the tangle crossing number with results which
parallel results for graph crossing numbers.
Hlin\v{e}n\'{y} and Salazar \cite{HlSa} studied the crossing number of
1-edge planar graphs (i.e., graphs in which there exists an edge whose removal results in
a planar graph). For each $k\geq 1$, they define a 1-edge planar graph
$G_k$ with $2k+4$ vertices, $6k+7$ edges, and crossing number $k$. We
find that the behavior is quite similar for the tangle crossing number.  First we establish an upper bound for $\crt(T)-\crt(T-e)$ given any
tanglegram $T$ and any matching edge $e$. Then for each $n\geq 4$, we
define a tanglegram of size $n$ with tangle crossing number $n-3$ for
which there is a single matching edge whose removal yields a planar
subtanglegram. In summary, we prove the following theorem in
Section 3:

\begin{theorem}\label{thm:edgerem}
  For any tanglegram $T$ of size $n\geq 3$ and any matching edge $e$
  in $T$, let $T-e$ be the tanglegram induced by deleting the
  endpoints of $e$ and suppressing the resulting degree two vertices (i.e., replace each degree two vertex $v$ by an edge
between the neighbors of $v$). Then $\crt(T) - \crt(T-e) \leq n-3$. This
  inequality is best possible, even when $T-e$ is planar.
\end{theorem}

We then examine the largest tangle crossing number
of a tanglegram of size $n$ (an analogue of the crossing number of the complete graph on $n$ vertices).
It is well known (e.g. by the crossing
lemma or by the counting method) that the crossing number of the complete graph $K_n$ is
$\Theta(n^4)=\Theta\left(\binom{n}{2}^2\right)$.  We prove the following result in Section~\ref{sec:onehalf}:

\begin{theorem}\label{thm:limit}
  For any tanglegram $T$ of size $n$,
  $\crt(T)<\frac{1}{2}\binom{n}{2}$. If $\gamma(n)$ is the maximum
  tangle crossing number among all tanglegrams of size $n$, then
\[\lim_{n\rightarrow\infty} \frac{\gamma(n)}{\binom{n}{2}} = \frac{1}{2}.\]
\end{theorem}
Interestingly, the structure of a size $n$ tanglegram with maximum tangle crossing number remains unknown.

We conclude with a polynomial time algorithm for computing lower
bounds on the tangle crossing number in Section~\ref{lowerb}. Drawing random tanglegrams of size $n$ from a uniform distribution, we give computational evidence that these lower bounds are $\Theta(n^2)$ with high probability, thus matching the result of Czabarka, Sz\'ekely, Wagner~\cite{CSW} that such a tanglegram has tangle crossing number $\Theta(n^2)$ with high probability.

\section{Preliminaries}\label{sec:pre}

Before delving into the proofs of our main theorems, we need to
establish some terminology and more formal definitions. A rooted
binary tree is a tree in which one vertex is designated as the root
and each vertex has either 0 or 2 children. A vertex with 0 children
is a \emph{leaf}. A vertex with 2 children is called an \emph{internal
  vertex}. Thinking of the root as a common ancestor to all other
vertices, the notions of \emph{descendant}, \emph{parent},
\emph{children} and \emph{sibling} become clear. If $B$ is a rooted
binary tree, a subset of the leaves of $B$ induces a binary subtree
$B'$, obtained from the smallest subtree of $B$ which contains the considered subset of leaves, by suppressing all
degree 2 vertices and choosing as the root of $B'$ the vertex which
was closest to the root of $B$. For any internal vertex $v$ of $B$,
the subtree induced by the leaves which are descendants of $v$ is a
\emph{clade} of $B$ at $v$, see Figure~\ref{fig:clade} for an example. If the two children of $v$ are leaves,
then the corresponding clade is called a \emph{cherry}.

\begin{figure}[ht]
    \centering
    \begin{tikzpicture}[yscale=0.8,scale=0.5,every node/.style={draw,circle,black,inner sep=2pt},
every picture/.style={thick},
leavesnode/.style={circle, draw, inner sep=1pt},scale=0.75]

% Left tanglegram
\begin{scope}

% Nodes for right tree of left tanglegram
\node (R0) at (0,0) {};
\node (R1) at (-1,1) {};
\node (R2) at (0,2) {};
\node (R3) at (-3,3) {};
\node (R4) at (0,4) {};
\node (R5) at (-1,5) {};
\node (R6) at (0,6) {};
\node (R7) at (-7,7) {};
\node[fill=black] (R8) at (0,8) {};
\node[fill=black] (R9) at (0,10) {};
\node[fill=black, label={[label distance=-1pt]180:$v$}] (R10) at (-3,11) {};
\node[fill=black] (R11) at (-2,12) {};
\node[fill=black] (R12) at (0,12) {};
\node[fill=black] (R13) at (-1,13) {};
\node[fill=black] (R14) at (0,14) {};

% Edges for right tree of left tanglegram
\draw (R0)--(R1);
\draw (R2)--(R1);
\draw (R3)--(R1);
\draw (R3)--(R5);
\draw (R5)--(R4);
\draw (R5)--(R6);
\draw (R7)--(R3);
\draw (R7)--(R10);
\draw (R10)--(R8);
\draw (R10)--(R11);
\draw (R13)--(R12);
\draw (R13)--(R14);
\draw (R11)--(R9);
\draw (R11)--(R13);

\end{scope}

\end{tikzpicture}
    \caption{The clade at $v$ is the subtree induced by the black leaves, namely the subtree induced by the vertices in black.}
    \label{fig:clade}
  \end{figure}

A \emph{tanglegram layout} is a straight-line drawing in the plane of
two rooted binary trees, $L$ and $R$, each with $n$ leaves and a
perfect matching $M$ between their leaves (each leaf of $L$ paired
with a unique leaf of $R$) having the following properties:
\begin{itemize}
\item A plane drawing of $L$ appears in the half plane $x\leq 0$ with
  only the leaves of $L$ on the line $x=0$.
\item A plane drawing of $R$ appears in the half plane $x\geq 1$ with
  only the leaves of $R$ on the line $x=1$.
\item The matching is represented by a (straight-line) drawing of edges connecting each
  leaf of $L$ with the appropriate leaf of $R$.
\end{itemize}
The crossing number of such a layout is precisely the number of unordered pairs
of matching edges which cross. As there are $n$ matching edges, the
crossing number is clearly at most $\binom{n}{2}$.

To transform one layout into another, we define a \emph{switch}. First
observe that a layout induces a total order on the leaves of $L$ by
the $y$-coordinate of the leaves on the line $x=0$. Now each internal
vertex $v$ of $L$ has two children $v_1$ and $v_2$. To make a switch
at $v$, redraw the tree $L$ so that in the new layout, the order of
leaves $\ell$ and $\ell'$ is reversed if and only if one was a leaf
in the clade at $v_1$ and the other was a leaf in the clade at
$v_2$. The resulting tanglegram layout displays the new drawing of
$L$, an unchanged drawing of $R$, and the same matching edges drawn as straight-lines and connecting the appropriate pairs of
leaves, for example see Figure~\ref{fig:switch}. Switch operations at internal vertices of $R$ are defined
analogously. Observe that the switch operation defines an equivalence
relation on the set of tanglegram layouts and each equivalence class
will be called a \emph{tanglegram}, denoted by the triple $(L,R,M)$.

\begin{figure}[ht]
    \centering
    \begin{tikzpicture}[yscale=0.8,scale=0.5,every node/.style={draw,circle,black,inner sep=2pt},
every picture/.style={thick},
leavesnode/.style={circle, draw, inner sep=1pt},scale=0.65,xscale=-1]

\begin{scope}

\node (L0) at (0,0) {};
\node (L1) at (-1,1) {};
\node (L2) at (0,2) {};
\node (L3) at (-3,3) {};
\node (L4) at (0,4) {};
\node (L5) at (-1,5) {};
\node (L6) at (0,6) {};
\node (L7) at (-7,7) {};
\node (L8) at (0,8) {};
\node (L9) at (-1,9) {};
\node (L10) at (0,10) {};
\node (L11) at (-3,11) {};
\node (L12) at (0,12) {};
\node (L13) at (-1,13) {};
\node (L14) at (0,14) {};

\draw (L0)--(L1);
\draw (L2)--(L1);
\draw (L3)--(L1);
\draw (L3)--(L5);
\draw (L5)--(L4);
\draw (L5)--(L6);
\draw (L7)--(L3);
\draw (L7)--(L11);
\draw (L9)--(L8);
\draw (L9)--(L10);
\draw (L9)--(L8);
\draw (L9)--(L10);
\draw (L13)--(L12);
\draw (L13)--(L14);
\draw (L11)--(L9);
\draw (L11)--(L13);

\begin{scope}[xscale=-1,xshift=-3cm]
\node (R0) at (0,0) {};
\node (R1) at (-1,1) {};
\node (R2) at (0,2) {};
\node (R3) at (-3,3) {};
\node (R4) at (0,4) {};
\node (R5) at (-1,5) {};
\node (R6) at (0,6) {};
\node (R7) at (-7,7) {};
\node[fill=black] (R8)[label={[label distance=-1pt]-135:$v_{2}$}] at (0,8) {};
\node[fill=black] (R9) at (0,10) {};
\node[fill=black, label={[label distance=-1pt]180:$v$}] (R10) at (-3,11) {};
\node[fill=black, label={[label distance=-1pt]135:$v_{1}$}] (R11) at (-2,12) {};
\node[fill=black] (R12) at (0,12) {};
\node[fill=black] (R13) at (-1,13) {};
\node[fill=black] (R14) at (0,14) {};

\draw (R0)--(R1);
\draw (R2)--(R1);
\draw (R3)--(R1);
\draw (R3)--(R5);
\draw (R5)--(R4);
\draw (R5)--(R6);
\draw (R7)--(R3);
\draw (R7)--(R10);
\draw (R10)--(R8);
\draw (R10)--(R11);
\draw (R13)--(R12);
\draw (R13)--(R14);
\draw (R11)--(R9);
\draw (R11)--(R13);
\end{scope}

% Matching edges for left tanglegram
% Make sure these are the same below for the right tanglegram so that they are equivalent.
\draw (L0)--(R9);
\draw (L2)--(R6);
\draw (L4)--(R8);
\draw (L6)--(R4);
\draw (L8)--(R0);
\draw (L10)--(R14);
\draw (L12)--(R2);
\draw (L14)--(R12);


\end{scope}

\begin{scope}[xshift=20cm]

\node (L0) at (0,0) {};
\node (L1) at (-1,1) {};
\node (L2) at (0,2) {};
\node (L3) at (-3,3) {};
\node (L4) at (0,4) {};
\node (L5) at (-1,5) {};
\node (L6) at (0,6) {};
\node (L7) at (-7,7) {};
\node (L8) at (0,8) {};
\node (L9) at (-1,9) {};
\node (L10) at (0,10) {};
\node (L11) at (-3,11) {};
\node (L12) at (0,12) {};
\node (L13) at (-1,13) {};
\node (L14) at (0,14) {};

\draw (L0)--(L1);
\draw (L2)--(L1);
\draw (L3)--(L1);
\draw (L3)--(L5);
\draw (L5)--(L4);
\draw (L5)--(L6);
\draw (L7)--(L3);
\draw (L7)--(L11);
\draw (L9)--(L8);
\draw (L9)--(L10);
\draw (L9)--(L8);
\draw (L9)--(L10);
\draw (L13)--(L12);
\draw (L13)--(L14);
\draw (L11)--(L9);
\draw (L11)--(L13);

\begin{scope}[xscale=-1,xshift=-3cm]

\node (R0) at (0,0) {};
\node (R1) at (-1,1) {};
\node (R2) at (0,2) {};
\node (R3) at (-3,3) {};
\node (R4) at (0,4) {};
\node (R5) at (-1,5) {};
\node (R6) at (0,6) {};
\node (R7) at (-7,7) {};

\begin{scope}[yshift=6cm]
\node[fill=black] (R8)[label={[label distance=-1pt]135:$v_{2}$}] at (0,8) {};
\end{scope}

\node[fill=black,label={[label distance=-1pt]180:$v$}] (R10) at (-3,11) {};

\begin{scope}[yshift=-2cm]
\node[fill=black] (R9) at (0,10) {};
\node[fill=black,label={[label distance=-1pt]-135:$v_{1}$}] (R11) at (-2,12) {};
\node[fill=black] (R12) at (0,12) {};
\node[fill=black] (R13) at (-1,13) {};
\node[fill=black] (R14) at (0,14) {};
\end{scope}

\draw (R0)--(R1);
\draw (R2)--(R1);
\draw (R3)--(R1);
\draw (R3)--(R5);
\draw (R5)--(R4);
\draw (R5)--(R6);
\draw (R7)--(R3);
\draw (R7)--(R10);
\draw (R10)--(R8);
\draw (R10)--(R11);
\draw (R13)--(R12);
\draw (R13)--(R14);
\draw (R11)--(R9);
\draw (R11)--(R13);
\end{scope}

% Matching edges for right tanglegram
% Make sure these are the same above for the left tanglegram so that they are equivalent.
\draw (L0)--(R9);
\draw (L2)--(R6);
\draw (L4)--(R8);
\draw (L6)--(R4);
\draw (L8)--(R0);
\draw (L10)--(R14);
\draw (L12)--(R2);
\draw (L14)--(R12);

\end{scope}


\end{tikzpicture}
    \caption{Two tanglegram layouts. Note that one layout is obtained from the other after a switch at vertex $v$. Thus both tanglegram layouts belong to the same tanglegram.}
    \label{fig:switch}
  \end{figure}

Let $T=(L,R,M)$ be a tanglegram. The \textit{size} of $T$ is the size
of the matching $M$ (also the number of leaves in $L$ and the number
of leaves in $R$). The \emph{tangle crossing number} of $T$, denoted
$\crt(T)$, is the minimum number of pairs of edges that cross, among
all layouts of $T$. If $T$ has size $n$ then one can easily deduce
that $\crt(T)\leq \binom{n}{2}$. A tanglegram is \textit{planar} provided $\crt(T)=0$.

Given a tanglegram $T=(L,R,M)$, a subset $M'$ of $M$ induces a
\emph{subtanglegram} $T'=(L',R',M')$ where $L'$ is the subtree of $L$
induced by leaves of $L$ which are endpoints of edges in $M'$ and $R'$
is defined similarly.

We let $\gamma(n)$ to denote the maximum tangle crossing number among all
tanglegrams of size $n$. In addition, we utilize the now standard notation $[n]$ for the set $\{1,2,\ldots, n\}$.

\section{Subtanglegrams of size \texorpdfstring{$n-1$}{n-1}}

In a tanglegram of size $n$, the tangle crossing number is at most $\frac{1}{2}\binom{n}{2}$ (Theorem~\ref{thm:limit}). Given a tanglegram with tangle crossing number close to this upper bound, on average, each matching edge crosses
one fourth of all the other matching edges. We explore the \emph{maximum}
number of crossings a single edge could contribute to the overall
tangle crossing number. Phrased another way, for any tanglegram $T$ of
size $n$ and subtanglegram $T'$ of size $n-1$, we determine the
maximum value of $\crt(T)-\crt(T')$.  The result is given in
Theorem~\ref{thm:edgeremoval}, an upper bound which
Theorem~\ref{thm:tight} shows to be tight, even for tanglegrams with
$T'$ planar. These two theorems together complete the proof of
Theorem~\ref{thm:edgerem}.

 Throughout this section, given
a tanglegram $T=(L,R,M)$ and $e\in M$, we use $T-e$ to denote the
subtanglegram of $T$ induced by edges in $M-e$.

\begin{theorem}
\label{thm:edgeremoval}
If $T = (L,R,M)$ is a tanglegram of size $n \geq 3$ and $e$ is any matching
edge of $T$, then \[\crt(T) - \crt(T-e) \leq n - 3.\]
\end{theorem}

\begin{proof} We will proceed by induction on $n$.  For the case $n=3$ we argue as
follows. Each planar drawing of a tree
determines a permutation its leaves; and if a tanglegram layout is planar, then the order of the
leaves of $R$ is uniquely determined by the order of the leaves of $L$ and the matching. There are $4$
planar drawings of $L$ and $4$ planar drawings of $R$. Given a planar drawing of $L$ and a matching, we
have $4$ possible orders on the leaves of $R$ that could potentially give a planar layout provided
$R$ can be drawn in a planar way giving that order. As there are $6$ permutations of the leaves of
$R$ and $4$ of these are planar, only $2$ permutations of the leaves of $R$ are non-planar, therefore
there are at least $4-2=2$ planar layouts for the tanglegram.
%If $T$ is a tanglegram of size $3$, then there are four planar drawings of $L$ and four planar drawings of $R$.  Since there are six permutations on three objects, any tanglegram $T$ of size $3$ has at least $4+4-6=2$ drawings without crossings.  Therefore, $\crt(T)=0$ for any tanglegram $T$ of size at most $3$, and the theorem holds for $n\le 3$.}

  Let $n\ge 4$ and suppose that in every tanglegram of size $n-1$, each
  edge contributes at most $(n-1)-3$ to the tangle crossing number. Fix a tanglegram $T = (L,R,M)$ of size $n$, and let
  $e\in M$ be an arbitrary matching edge of $T$. Say $e$ has endpoints
  $u$ in $L$ and $v$ in $R$.  Fix an optimal layout $D'$ of
  $T - e = (L_{u}, R_{v}, M-e)$ with the fewest number of crossings.

  In $L$, let $w_{L'}$ be the parent of $u$ and let $L'$ be the clade at the other child of $w_{L'}$. (Similarly, define $w_{R'}$ and $R'$.)
  There are two planar drawings of $L$ whose subdrawings of $L_u$ agree with the drawing of $L_u$ in $D'$, one with $u$ immediately
  above the leaves of $L'$ and one with $u$ immediately below the leaves of $L'$. The ordering of the leaves of $L_u$ in each of these
  drawings of $L$ is exactly the same as the ordering of the leaves in the drawing of $L_u$ in $D'$. Further, one of these drawings of
  $L$ can be obtained from the other by making a switch at $w_{L'}$. A similar claim can be made about $R$, $v$, $R_v$, $w_{R'}$ and $R'$.
  Figure~\ref{fig:illustration} uses dashed lines to indicate the two potential positions of $u$ and for $v$ in a drawing of $T$.

    \begin{figure}[ht]
    \centering
    \begin{tikzpicture}[scale=0.5,
every picture/.style={thick}]
\tikzstyle{none}=[inner sep=0pt]
\tikzstyle{invisible}=[circle,fill=Black,draw=Black]
\tikzstyle{simple}=[-,draw=Black,line width=2.000]
		\node [style=none] (0) at (0, 0) {};
		\node [draw,circle,black,inner sep=2pt,label=west:$u$] (1) at (0, 3) {};
		\node [draw,circle,black,inner sep=2pt,label=west:$u$] (2) at (0, 11) {};
		\node [style=none] (3) at (0, 14) {};
		\node [style=none] (4) at (-7, 7) {};
		\node [draw,circle,black,inner sep=2pt,label=west:$w_{L'}$] (5) at (-4, 7) {};
		\node [style=none] (6) at (0, 9) {};
		\node [style=invisible] (7) at (-3, 7) {};
		\node [style=none] (8) at (0, 5) {};
		\node [style=none] (9) at (-1, 7) {{\Large$L'$}};
		\node [draw,circle,black,inner sep=2pt,label=east:$v$] (10) at (4, 3) {};
		\node [style=none] (11) at (4, 9) {};
		\node [style=none] (12) at (5, 7) {{\Large$R'$}};
		\node [draw,circle,black,inner sep=2pt,label=east:$w_{R'}$] (13) at (8, 7) {};
		\node [style=none] (14) at (4, 14) {};
		\node [style=none] (15) at (4, 5) {};
		\node [style=none] (16) at (4, 0) {};
		\node [draw,circle,black,inner sep=2pt,label=east:$v$] (17) at (4, 11) {};
		\node (18) at (11, 7) {};
		\node [style=invisible] (19) at (7, 7) {};
		\node (20) at (-9, 7) {{\Large$L$}};
		\node (21) at (13, 7) {{\Large$R$}};

		\draw (3.center) to (4.center);
		\draw (4.center) to (0.center);
		\draw [dashed,style=simple] (2) to (5);
		\draw [dashed,style=simple] (5) to (1);
		\draw [style=simple] (6.center) to (7);
		\draw [style=simple] (7) to (8.center);
		\draw [style=simple] (8.center) to (6.center);
		\draw [style=simple] (7) to (5);
		\draw (14.center) to (18.center);
		\draw (18.center) to (16.center);
		\draw [dashed,style=simple] (17) to (13);
		\draw [dashed,style=simple] (13) to (10);
		\draw [style=simple] (11.center) to (19);
		\draw [style=simple] (19) to (15.center);
		\draw [style=simple] (15.center) to (11.center);
		\draw [style=simple] (19) to (13);

\end{tikzpicture}
    \caption{An illustration of the potential positions of $u$ and $v$ in the proof of Theorem~\ref{thm:edgeremoval}.}
    \label{fig:illustration}
  \end{figure}

 We claim that there is drawing $D$ of $T$ using one of these two drawings of $L$ and one of these two drawings of $R$ in which the matching edge $e$ crosses at most $n-3$ edges. This is sufficient to complete the proof as the number of crossings between two edges of $M-e$ in $D$ is exactly $\crt(T-e)$ (because the underlying drawing of $T-e$ remained unchanged) which implies $\crt(T) \leq \crt(D) \leq \crt(T-e) + (n-3)$ as desired.

 First observe that $L'$ and $R'$ each have at least one leaf. There are two cases to consider: (1) $L'$ and $R'$ each have exactly one leaf and they are matched in $M-e$, or (2) there is a leaf in $L'$ and a leaf in $R'$ which are not matched with one another.

   For the first case, let $f$ be the edge matching the single leaf in $L'$ with the single leaf in $R'$. Consider the drawing of $T$ with $u$ above $L'$ and $v$ above $R'$ so that   $e$ is above $f$; see Figure~\ref{fig:threecases}(a). Suppose, for
  contradiction, that $e$ participates in strictly more than $n-3$
  crossings in this drawing of $T$. As $e$ does not cross itself or
  $f$, matching edge $e$ must cross every other edge in $M$.
  Since there are no leaves between the left endpoints of $e$ and $f$ and
  no leaves between the right endpoints of $e$ and $f$, it follows
  that $f$ also participates in $n - 2$ crossings in this drawing of
  $T$.  As the drawing of $T-e$ was optimal, we see that $f$
  contributes $n-2$ to the tangle crossing number of tanglegram $T-e$
  which had size $n-1$.  However, by the induction hypothesis, each edge in
  $T-e$ contributes at most $(n-1)-3$ crossings to $\crt(T-e)$, a
  contradiction.

  For the second case, let $u_{L'}$ be a leaf in $L'$ and $v_{R'}$ be a leaf in $R'$ which are not matched to each other. We say $u_{L'}$ (respectively, $v_{R'}$) is ``matched upward'' if the
  leaf to which it is matched is at least as high as the lowest leaf
  of $R^\prime$ (respectively, $L^\prime$). The leaf $u_{L'}$
  (respectively, $v_{R'}$) is ``matched downward'' if the leaf to
  which it is matched is no higher than the highest leaf of $R^\prime$
  (respectively, $L^\prime$).

  Let $f_1$ and $f_2$ be the matching edges, one with endpoint $u_{L'}$ and the other with endpoint $v_{R'}$. If $u_{L'}$ and $v_{R'}$
  are both matched upward (respectively, downward), draw the vertex
  $u$ below (respectively, above) $L^\prime$ and the vertex $v$ below
  (respectively, above) $R^\prime$; see Figure~\ref{fig:threecases}(b).  On the other hand, if $u_{L'}$ is
  matched to a leaf higher (lower) than the leaves of $R'$ and
  $v_{R'}$ is matched to a leaf lower (higher) than the leaves of
  $L'$, then draw $u$ directly below (above) the leaves of $L'$ and
  $v$ directly above (below) the leaves of $R'$; see Figure~\ref{fig:threecases}(c).  In each of these
  cases, the edge $e$ crosses neither $f_1$ nor $f_2$, and therefore
  crosses at most $n-3$ other edges, from which
  $\crt(T) - \crt(T - e) \leq n-3$ follows.
  \end{proof}

    \begin{figure}[ht]
    \begin{center}
%%%%%%%
%%% case (a)
%%%%%%%
\begin{tikzpicture}[scale=0.2,
every node/.style={circle,draw=black, fill=white, inner sep=2pt},
every label/.style={rectangle,draw=none,fill=none}]

\draw (-2,-7) -- (-9,0) -- (-2,7);
\draw (2,-7) -- (9,0) -- (2,7);
\node[rectangle,draw=none] at (-7,5) {$L$};
\node[rectangle,draw=none] at (7,-5) {$R$};

\node[label={left:$u$}] (u) at (-2,-3) {};
\node[label={left:$w_{L'}$}] (wl) at (-4,-5) {};
\node (fl) at (-2,-7) {};
\draw[line width=2pt] (u) -- (wl) -- (fl);

\node[label={right:$v$}] (v) at (2,7) {};
\node[label={right:$w_{R'}$}] (wr) at (4,5) {};
\node (fr) at (2,3) {};
\draw[line width=2pt] (v) -- (wr) -- (fr);

\draw[line width=2pt] (u) --node[midway,left,draw=none,fill=none]{$e$} (v);
\draw[line width=2pt] (fl) --node[midway,right,draw=none,fill=none]{$f$} (fr);

\node[draw=none,rectangle] at (0,-9) {(a)};
\end{tikzpicture}
%%%%%%%
\hfil
%%% case (b)
%%%%%%%
\begin{tikzpicture}[scale=0.2,
every node/.style={circle,draw=black, fill=white, inner sep=2pt},
every label/.style={rectangle,draw=none,fill=none}]

\draw (-2,-7) -- (-9,0) -- (-2,7);
\draw (2,-7) -- (9,0) -- (2,7);
\node[rectangle,draw=none] at (-7,5) {$L$};
\node[rectangle,draw=none] at (7,5) {$R$};

\node[label={left:$u$}] (u) at (-2,-5) {};
\node[label={[fill=white]225:$w_{L'}$}] (wl) at (-7,0) {};
\node[fill=black] (fl) at (-6,1) {};
\draw[line width=2pt] (u) -- (wl) -- (fl);
\draw[line width=2pt] (fl) -- (-2,-3) -- (-2,5) -- (fl);

\node[label={right:$v$}] (v) at (2,-5) {};
\node[label={[fill=white]-45:$w_{R'}$}] (wr) at (7,0) {};
\node[fill=black] (fr) at (6,1) {};
\draw[line width=2pt] (v) -- (wr) -- (fr);
\draw[line width=2pt] (fr) -- (2,-3) -- (2,5) -- (fr);

%\draw[draw=none,fill=gray,fill opacity=0.5] (1,-3) -- (-2,-1) -- (1,7);
%\draw[draw=none,fill=gray,fill opacity=0.5] (-1,-3) -- (2,-1) -- (-1,7);
\node[label={[label distance=-3pt,xshift=-8pt]above:\footnotesize $u_{L'}$}] (ul) at (-2,-1) {};
\node[label={[label distance=-3pt,xshift=8pt]above:\footnotesize $v_{R'}$}] (vr) at (2,-1) {};

\node (ulp) at (2,6.5) {};
\node (vrp) at (-2,3) {};
\draw[line width=2pt] (ul) --node[near end,draw=none,fill=none,xshift=-5pt,yshift=3pt] {\footnotesize $f_1$} (ulp);
\draw[line width=2pt] (vr) --node[near start,draw=none,fill=none,xshift=-5pt,yshift=-3pt] {\footnotesize $f_2$} (vrp);


\draw[line width=2pt] (u) -- (v);

\node[draw=none,rectangle] at (0,-9) {(b)};
\end{tikzpicture}
%%%%%%%
\hfil
%%% case (c)
%%%%%%%
\begin{tikzpicture}[scale=0.2,
every node/.style={circle,draw=black, fill=white, inner sep=2pt},
every label/.style={rectangle,draw=none,fill=none}]

\draw (-2,-7) -- (-9,0) -- (-2,7);
\draw (2,-7) -- (9,0) -- (2,7);
\node[rectangle,draw=none] at (-7,5) {$L$};
\node[rectangle,draw=none] at (7,5) {$R$};

\node[label={left:$u$}] (u) at (-2,-5) {};
\node[label={[fill=white]225:$w_{L'}$}] (wl) at (-7,0) {};
\node[fill=black] (fl) at (-6,1) {};
\draw[line width=2pt] (u) -- (wl) -- (fl);
\draw[line width=2pt] (fl) -- (-2,-3) -- (-2,5) -- (fl);

\node[label={right:$v$}] (v) at (2,5) {};
\node[label={[fill=white]-45:$w_{R'}$}] (wr) at (7,0) {};
\node[fill=black] (fr) at (6,-1) {};
\draw[line width=2pt] (v) -- (wr) -- (fr);
\draw[line width=2pt] (fr) -- (2,3) -- (2,-5) -- (fr);

%\draw[draw=none,fill=gray,fill opacity=0.5] (1,5.2) -- (-2,-1) -- (1,7);
%\draw[draw=none,fill=gray,fill opacity=0.5] (-1,-5.2) -- (2,1) -- (-1,-7);
\node[label={[label distance=-3pt,xshift=-8pt]above:\footnotesize $u_{L'}$}] (ul) at (-2,-1) {};
\node[label={[label distance=-3pt,xshift=8pt]below:\footnotesize $v_{R'}$}] (vr) at (2,1) {};

\node (ulp) at (2,6.5) {};
\node (vrp) at (-2,-6.5) {};
\draw[line width=2pt] (ul) --node[midway,draw=none,fill=none,xshift=-5pt,yshift=3pt] {\footnotesize $f_1$} (ulp);
\draw[line width=2pt] (vr) --node[midway,draw=none,fill=none,xshift=5pt,yshift=-3pt] {\footnotesize $f_2$} (vrp);

\draw[line width=2pt] (u) -- (v);

\node[draw=none,rectangle] at (0,-9) {(c)};
\end{tikzpicture}
\end{center}

    \caption{An illustration of the possible relations between $L'$ and $R'$ in the proof of Theorem~\ref{thm:edgeremoval}:  (a) $L'$ and $R'$ each have exactly one leaf and they are matched in $M-e$. (b) $u_{L'}$ an d $v_{R'}$ are not matched to each other and are both matched upward.
%The gray areas indicate the possible places of the matching edges for $u_L'$ and $v_{R'}$, respectively.
(c) $u_{L'}$ is matched to a leaf higher than the leaves of $R'$, and $v_{R'}$ is matched to a leaf lower than the leaves of $L'$.}
    \label{fig:threecases}
  \end{figure}


Now we prove that the inequality in Theorem~\ref{thm:edgeremoval} is
best possible. To do so, we present an infinite family of tanglegrams
$\{P_n: n\geq 4\}$ such that $P_n$ has size $n$, tangle crossing number $n-3$, and
there exists a matching edge $e$ such that $\crt(P_n-e)=0$. We say
$P_n$ is \emph{1-edge tangle planar} as $P_n$ is not planar but
there is a matching edge $e$ such that the subtanglegram $P_n-e$ is
planar. The two binary trees in $P_n$ are rooted caterpillars.

\begin{definition}
  The \emph{rooted caterpillar} $C_n$ of size $n$ is the unique rooted
  binary tree with $n$ leaves such that there are two leaves of
  distance $n-1$ from the root and for each $i\in [n-2]$ there is one
  leaf of distance $i$ from the root.
  (See Figure \ref{fig:c6} for an example.)
\end{definition}

\begin{figure}[ht]
\centering
\begin{tikzpicture}[yscale=0.8,scale=0.4,every node/.style={draw,circle,black,inner sep=2pt},
every picture/.style={thick},
leavesnode/.style={circle, draw, inner sep=1pt}]
\node (0) at (0, 0) {};
\node (1) at (0, 2) {};
\node (2) at (-1, 1) {};
\node (3) at (0, 4) {};
\node (4) at (-2, 2) {};
\node (5) at (0, 6) {};
\node (6) at (-3, 3) {};
\node (7) at (-3, 3) {};
\node (8) at (0, 8) {};
\node (9) at (-4, 4) {};
\node (10) at (0, 10) {};
\node (11) at (-5, 5) {};

\draw (11) -- (9);
\draw (9) -- (6);
\draw (6) to (4);
\draw (4) to (2);
\draw (2) to (0);
\draw (2) to (1);
\draw (4) to (3);
\draw (6) to (5);
\draw (9) to (8);
\draw (11) to (10);
\end{tikzpicture}
\caption{The caterpillar $C_6$.}
\label{fig:c6}
\end{figure}

\begin{definition}
  For each $n\ge 4$, we define the \emph{caterpillar tanglegram}
  $P_n = (L_n,R_n,M_n)$ as follows: $L_n$ and $R_n$ are copies of the
  rooted caterpillar $C_n$. We label the leaves of $L_n$ as $u_i$,
  where $i$ is the leaf's distance from the root. Since there are
  precisely two leaves at distance $n-1$, we arbitrarily label one of
  these $u_n$ instead. Similarly, the leaves of $R_n$ are labeled
  using $v_i$. Finally, we construct the matching
  $M_n = \{u_iv_{n-i} \mid i \in [n-1]\} \cup \{u_nv_n\}$. (See Figure
  \ref{fig:p8} for an example.)
\end{definition}

\begin{figure}[ht]
  \centering
  \begin{tikzpicture}[yscale=0.8,scale=0.5,every node/.style={draw,circle,black,inner sep=2pt},
every picture/.style={thick},
leavesnode/.style={circle, draw, inner sep=1pt}]
\begin{scope}
\node[label=west:$u_7$] (0) at (0, 0) {};
\node[label=west:$u_8$] (1) at (0, 2) {};
\node[label=west:$u_6$] (3) at (0, 4) {};
\node[label=west:$u_5$] (5) at (0, 6) {};
\node[label=west:$u_4$] (8) at (0, 8) {};
\node[label=west:$u_3$] (10) at (0, 10) {};
\node[label=west:$u_2$] (11) at (0, 12) {};
\node[label=west:$u_1$] (12) at (0, 14) {};
\node[label=east:$v_8$] (16) at (3, 12) {};
\node[label=east:$v_4$] (17) at (3, 6) {};
\node[label=east:$v_5$] (22) at (3, 8) {};
\node[label=east:$v_7$] (26) at (3, 14) {};
\node[label=east:$v_6$] (27) at (3, 10) {};
\node[label=east:$v_3$] (28) at (3, 4) {};
\node[label=east:$v_1$] (30) at (3, 0) {};
\node[label=east:$v_2$] (31) at (3, 2) {};
\end{scope}

\node (2) at (-1, 1) {};
\node (4) at (-2, 2) {};
\node (6) at (-3, 3) {};
\node (7) at (-3, 3) {};
\node (9) at (-4, 4) {};
\node (13) at (-5, 5) {};
\node (14) at (-6, 6) {};
\node (15) at (-7, 7) {};
\node (18) at (8, 9) {};
\node (19) at (4, 13) {};
\node (20) at (6, 11) {};
\node (21) at (5, 12) {};
\node (23) at (7, 10) {};
\node (24) at (9, 8) {};
\node (25) at (10, 7) {};
\node (29) at (6, 11) {};


\draw (12) to (15);
\draw (15) to (14);
\draw (14) to (13);
\draw (13) to (9);
\draw (9) to (6);
\draw (6) to (4);
\draw (4) to (2);
\draw (2) to (0);
\draw (2) to (1);
\draw (4) to (3);
\draw (6) to (5);
\draw (9) to (8);
\draw (13) to (10);
\draw (14) to (11);
\draw (30) to (25);
\draw (25) to (24);
\draw (24) to (18);
\draw (18) to (23);
\draw (23) to (29);
\draw (29) to (21);
\draw (21) to (19);
\draw (19) to (26);
\draw (19) to (16);
\draw (21) to (27);
\draw (29) to (22);
\draw (23) to (17);
\draw (18) to (28);
\draw (24) to (31);
\draw (12) to (26);
\draw (0) to (30);
\draw (16.south west) to (1.north east);
\draw (3) to (31);
\draw (5) to (28);
\draw (8) to (17);
\draw (10) to (22);
\draw (11) to (27);
\end{tikzpicture}
  \caption{The caterpillar tanglegram $P_8$.}
  \label{fig:p8}
\end{figure}


\begin{theorem}\label{thm:tight}
  For each $n \geq 4$, the caterpillar tanglegram $P_n$ is 1-edge
  tangle planar and has tangle crossing number $n-3$.
\end{theorem}
\begin{proof}
  Note that the tanglegram $P_{n}-u_{n}v_{n}$ is clearly a planar
  tanglegram (see Figure \ref{fig:p8}), so $P_n $ is 1-edge tangle
  planar. The same drawing demonstrates that $\crt(P_n) \leq n-3$. It
  remains to show that $\crt(P_n) \geq n-3$. Suppose, for
  contradiction, that there is some $k$ for which $\crt(P_k) <
  k-3$. Furthermore, let $k$ be the least index witnessing this strict
  inequality.

Since $P_3$ has a planar drawing, $k\geq 4$.
There are two cases for a fixed optimal drawing of $P_k$: at least one matching edge in the set $S=\{u_iv_{k-i} \mid 1 \leq i \leq k-1\}$ is part of a crossing or else none of them are.

In the former case, say the edge $u_jv_{k-j}\in S$ is part of a crossing. The subtanglegram induced by $M_k- u_jv_{k-j}$ is isomorphic to $P_{k-1}$ and has tangle crossing number at most $\crt(P_k)-1$. It follows that $\crt(P_{k-1}) \leq \crt(P_k) - 1 < (k - 1) - 3$, which contradicts the minimality of $k$.

  In the latter case, the subtanglegram $T=(L_T,R_T,M_T)$ induced by $S$ has a planar layout in $P_k$.  Any planar drawing of $L_T$ must have $u_1$ at the top or at the bottom.  Flipping the tanglegram if necessary, we may assume $u_1$ is at the top of the layout of $T$.  Since the drawing of $T$ is planar, $v_{k-1}$ is also at the top.  Similarly, $v_1$ and $u_{k-1}$ have to be at the bottom in the drawing of $T$.  It follows that every edge in $S'=\{u_iv_{k-i} \mid 2\leq i\leq k-2\}$ is in between $u_1v_{k-1}$ and $u_{k-1}v_1$.  Now consider the possible positions of $u_k$ and $v_k$ in $P_k$.  Since $u_k$ and $v_k$ has to be next to $u_{k-1}$ (at the bottom) and $v_{k-1}$ (at the top), respectively, the edge $u_kv_k$ is forced to pass through all edges in $S'$.  Therefore, the tangle crossing number is at least $|S'|=n-3$.
\end{proof}

\section{Maximizing the crossing number}
\label{sec:onehalf}

While a single edge  in a tanglegram of size $n$ can contribute up to $n-3$ to the tangle crossing number, not all matching edges can realize this many crossings in a drawing which minimizes the tangle crossing number. The aim of this section is to better understand the maximum tangle crossing number among tanglegrams of the same size. To prove Theorem~\ref{thm:limit}, we begin with the first part:

\begin{theorem}\label{thm:onehalf}
  If $T$ is a tanglegram of size $n$ then
  $\crt(T)<\frac{1}{2} \binom{n}{2}.$  Consequently,
   $$
  \limsup_{n\rightarrow\infty}
  \frac{\gamma(n)}{\binom{n}{2}}
  \leq
  \frac{1}{2}.
   $$
\end{theorem}

\begin{proof}
  Let $T=(L,R,M)$ be a tanglegram.
  Suppose $\crt(T)=k$ and let $D$ be a tanglegram layout of
  $T$ having $k$ crossings.  By making a switch at every internal
  vertex in $R$, we obtain a new layout $D'$ of $T$.  Note that in
  $D'$, the plane drawing of $R$ can be viewed as a reflection of
  the drawing of $R$ in $D$ across the line $y=0$, while the plane
  drawing of $L$ is the same in both $D$ and $D'$.  For any unordered pair of
  edges $\{e,f\}$ in $M$, $e$ and $f$ cross in $D$ if and
  only if they do not cross in $D'$. This implies that $D'$ has
  exactly $\binom{n}{2}-k$ crossings. Since $\crt(T)=k$, every layout
  has at least $k$ crossings.  Consequently, $\binom{n}{2}-k\geq k$
  and $\crt(T)=k\le \frac{1}{2}\binom{n}{2}$.

  Suppose that, contrary to our statement, $\crt(T)=\frac{1}{2}\binom{n}{2}$.
  It follows from our proof so far that any layout of $T$ has $\frac{1}{2}\binom{n}{2}$ crossings, and for
  any unordered pair $\{e,f\}$ of matching edges there is a layout in which they cross.
  Let $C$ be a cherry of $R$ with leaves $\ell_1$ and $\ell_2$
  incident with matching edges $e,f\in M$. As noted above, $e$ and $f$
  must cross in some layout $D$ of $T$. From $D$, we create
  a new layout $D''$ by making a switch at the parent of $\ell_1$ and
  $\ell_2$.  The number of crossings in $D''$ is
  $\frac{1}{2}\binom{n}{2}-1$, a contradiction.
  \end{proof}

To complete the proof of Theorem~\ref{thm:limit}, we
prove
\[\liminf_{n\rightarrow\infty}\dfrac{\gamma(n)}{\binom{n}{2}}\geq
  1/2\] by constructing for each $n\geq 4$ a family $\cT_n$ of tanglegrams of
  size $n$ such that
for any $\varepsilon>0$ and large enough $n$, for all $T\in\cT_n$
 $\crt(T) / \binom{n}{2} \geq \frac{1}{2} - \varepsilon$.

We begin by constructing a family $\cT_{k^2}$ for each integer $k\ge 2$.
Any $T\in\cT_{k^2}$ is the result of the following procedure:
Take an arbitrary $(2k+2)$-tuple of rooted binary trees
$(L_0,\ldots,L_k, R_0, \ldots, R_k)$, each of size $k$.
Label the $k$ leaves of $L_0$ with labels $\{1,2,\ldots, k\}$ arbitrarily. For
each $i\in [k]$, identify the root of $L_i$ with leaf $i$ in $L_0$ and
assign labels $\{v_{ij}: j\in [k]\}$ to the $k$ leaves of $L_i$. The result
is the rooted binary tree $L$ with $k^2$ leaves. Similarly, $R$ is
built from $(R_0, R_1, \ldots, R_k)$ with leaf labels
$\{w_{ij}: i,j\in [k]\}$.  The matching is defined as
$M=\{v_{ij}w_{ji}: i,j\in [k]\}$.

Figure~\ref{fig:tau9} shows a tanglegram in $\cT_9$.  The binary
trees $L_1$, $L_2$, $L_3$ are marked by dashed rectangles. The tree
$L_{0}$ is the subtree of $L$ consisting of the roots of $L_{1}, L_{2}$, $L_{3}$,
and their ancestors. Note that the trees $L_0, L_1, L_2,$ and
$L_3$ need not be isomorphic. They are only isomorphic here because
there is only one binary tree, up to isomorphism, with 3 leaves.
Further, for any pair of trees from $\{L_1, L_2, L_3\}$ and two trees from $\{R_1, R_2, R_3\}$,
there is at least one pair of edges which cross.


\begin{figure}[ht]
  \centering
  \begin{tikzpicture}[yscale=0.8,scale=0.5,every node/.style={draw,circle,black,inner sep=2pt},
every picture/.style={thick},
leavesnode/.style={circle, draw, inner sep=1pt}]

%%%Middle vertices and matching
\foreach \i in {1,2,3}{
\foreach \j in {1,2,3}{
\pgfmathsetmacro{\y}{int(24-6*\i-2*\j)}
\node [label={[label distance=-1pt]180:$v_{\i\j}$}](v\i\j) at (0,\y) {};
\node [label={[label distance=-1pt]0:$w_{\i\j}$}](w\i\j) at (4,\y) {};
}}
\foreach \i in {1,2,3}{
\foreach \j in {1,2,3}{
\draw (v\i\j) -- (w\j\i);
}}

%%%Left tree
\node (L1m) at (-1,15) {};
\node (L2m) at (-1,7) {};
\node (L3m) at (-1,1) {};
\node (L1r) at (-2,14) {};
\node (L2r) at (-2,8) {};
\node (L3r) at (-2,2) {};
\node (L0m) at (-4,5) {};
\node (L0r) at (-6,8) {};

\draw (L1m) -- (v11);
\draw (L1m) -- (v12);
\draw (L2m) -- (v22);
\draw (L2m) -- (v23);
\draw (L3m) -- (v32);
\draw (L3m) -- (v33);
\draw (L1r) -- (L1m);
\draw (L1r) -- (v13);
\draw (L2r) -- (v21);
\draw (L2r) -- (L2m);
\draw (L3r) -- (v31);
\draw (L3r) -- (L3m);
\draw (L0m) -- (L2r);
\draw (L0m) -- (L3r);
\draw (L0r) -- (L1r);
\draw (L0r) -- (L0m);

%%%Right tree
\node (R1m) at (5,13) {};
\node (R2m) at (5,7) {};
\node (R3m) at (5,1) {};
\node (R1r) at (6,14) {};
\node (R2r) at (6,8) {};
\node (R3r) at (6,2) {};
\node (R0m) at (8,11) {};
\node (R0r) at (10,8) {};

\draw (R1m) -- (w12);
\draw (R1m) -- (w13);
\draw (R2m) -- (w22);
\draw (R2m) -- (w23);
\draw (R3m) -- (w32);
\draw (R3m) -- (w33);
\draw (R1r) -- (w11);
\draw (R1r) -- (R1m);
\draw (R2r) -- (w21);
\draw (R2r) -- (R2m);
\draw (R3r) -- (w31);
\draw (R3r) -- (R3m);
\draw (R0m) -- (R1r);
\draw (R0m) -- (R2r);
\draw (R0r) -- (R0m);
\draw (R0r) -- (R3r);

%dashed rentangles
\draw [thin,dashed] (-2.5,11.5) rectangle (0.5,16.5);
\draw [thin,dashed] (-2.5,5.5) rectangle (0.5,10.5);
\draw [thin,dashed] (-2.5,-0.5) rectangle (0.5,4.5);
\draw [thin,dashed] (3.5,11.5) rectangle (6.5,16.5);
\draw [thin,dashed] (3.5,5.5) rectangle (6.5,10.5);
\draw [thin,dashed] (3.5,-0.5) rectangle (6.5,4.5);
\begin{scope}[every node/.style={rectangle}]
\node[left] at (-2.6,15) {$L_1$};
\node[left] at (-2.6,9) {$L_2$};
\node[left] at (-2.6,1) {$L_3$};
\node[right] at (6.6,15) {$R_1$};
\node[right] at (6.6,7) {$R_2$};
\node[right] at (6.6,1) {$R_3$};
\end{scope}

\end{tikzpicture}
  \caption{A tanglegram in $\cT_9$.}
  \label{fig:tau9}
\end{figure}

With a well-defined set of tanglegrams $\cT_{k^2}$ for each $k\geq 2$, we now define $\cT_n$ for any
integer $n$. Fix $n$ and choose $k$ such that $k^2 \leq n<(k+1)^2$.
Let $\cT_n$ be the set of
tanglegrams of size $n$ such that $T\in \cT_n$ if and only if there is a
tanglegram $T'\in \cT_{k^2}$ with $T'$ a subtanglegram of $T$.
Figure~\ref{fig:tau5} shows a tanglegram in $\cT_5$.  The tanglegram
with bold edges is a subtanglegram in $\cT_4$.

\begin{figure}[ht]
  \centering
  \begin{tikzpicture}[yscale=0.8,scale=0.5,every node/.style={draw,circle,black,inner sep=2pt},
every picture/.style={thick},
leavesnode/.style={circle, draw, inner sep=1pt}]
%%%Middle vertices
\foreach \i in {1,...,5}{
\pgfmathsetmacro{\y}{int(10-2*\i)}
\node (v\i) at (0,\y) {};
\node (w\i) at (2,\y) {};
}
%%%All other vertices
\node (v6) at (-1,1) {};
\node (v7) at (-1,5) {};
\node (v8) at (-3,3) {};
\node (v9) at (-4,4) {};
\node (w6) at (3,1) {};
\node (w7) at (3,7) {};
\node (w8) at (4,2) {};
\node (w9) at (6,4) {};

%%%Bolded edges
\begin{scope}[line width=2pt]
\draw (v6) -- (v8) -- (v7);
\draw (v2) -- (v7) -- (v3);
\draw (v4) -- (v6) -- (v5);
\draw (w1) -- (w7) -- (w2);
\draw (w7) -- (w9) -- (w8);
\draw (w3) -- (w8) -- (w6);
\draw (w6) -- (w5);
\foreach \i/\j in {2/1,3/3,4/2,5/5}{
\draw (v\i) -- (w\j);
}
\end{scope}
%%%Other edges
\draw (v1) -- (w4);
\draw (v1) -- (v9) -- (v8);
\draw (w4) -- (w6);

%%%Marks
% \begin{scope}[every node/.style={rectangle,draw=none}]
% \node[left] at (-0.1,8) {$v$};
% \node[right] at (2.1,2) {$w$};
% \node[left] at (-4.1,4) {new root};
% \node[right] at (3.1,1) {subdivision vertex};
% \end{scope}
\end{tikzpicture}
  \caption{A tanglegram in $\cT_{5}$.}
  \label{fig:tau5}
\end{figure}

\begin{theorem}\label{th:liminf}
\[\liminf_{n\rightarrow\infty}\frac{\gamma(n)}{\binom{n}{2}}\geq\frac{1}{2}.\]
\end{theorem}
\begin{proof}
First we show that for each $k\ge 2$ and $T\in\cT_{k^2}$, $\crt(T)\ge\binom{k}{2}^2$.
Observe that for each $i\in [k]$, $L_{i}$ is a clade of $L$ at one of
the leaves of $L_{0}$. Therefore in any tanglegram layout of $(L,R,M)$
all the leaves of $L_{i}$ appear forming a vertical consecutive block,
for each $i\in [k]$. A similar assertion holds for the leaves of
$R_{i}$, $i\in[k]$.  For any $\{i, j\}, \{a, b\}\subseteq [k]$, there
are 4 edges with both endpoints in the clades $L_i$, $L_j$, $R_a$, and
$R_b$. Because the leaves in a single clade form a vertical
consecutive block in any layout, either the edges $v_{i a}w_{ai}$ and
$v_{jb}w_{bj}$ or the edges $v_{ja}w_{aj}$ and $v_{ib}w_{bi}$ form a
crossing. As a result, $\crt(T) \geq \binom{k}{2}^2$.

As the tangle crossing number of each tanglegram in $\cT_{k^2}$ is
at least $\binom{k}{2}^2$, the tangle crossing number of each
tanglegram in $\cT_n$ with $n>k^2$ is also at least $\binom{k}{2}^2$.

 Let $n\ge 4$ and $k=\lfloor\sqrt{n}\rfloor$, so  $k^2 \leq n < (k+1)^2$. Observe that for each
  tanglegram $T\in \cT_n$, $\crt(T) \geq \binom{k}{2}^2$. Therefore
    \begin{align*}
      \frac{\gamma(n)}{\binom{n}{2}}
      \geq \dfrac{\displaystyle\max_{T\in \cT_n} \crt(T)}{\binom{n}{2}}
      \geq\frac{\binom{k}{2}^2}{\binom{(k+1)^2}{2}}
      &  = \frac{1}{2} \left(1-\frac{2}{k+2}\right) \left(1-\frac{2}{k+1}\right)^2\\
      & \geq  \frac{1}{2} \left(1-\frac{2}{\sqrt{n}+1}\right) \left(1-\frac{2}{\sqrt{n}}\right)^2.
      \end{align*}


As a result,
\[ \liminf_{n\rightarrow\infty} \frac{\gamma(n)}{\binom{n}{2}} \geq
  \liminf_{n\rightarrow\infty} \frac{1}{2}
  \left(1-\frac{2}{\sqrt{n}+1}\right)
  \left(1-\frac{2}{\sqrt{n}}\right)^2 =\frac{1}{2}.\qedhere\]
\end{proof}

Theorems~\ref{thm:onehalf} and~\ref{th:liminf} complete the proof of
Theorem~\ref{thm:limit}.



\section{Lower bound of the tangle crossing number} \label{lowerb}

%HS: This paragraph is new:
Computing the exact value of $\crt(T)$ for an arbitrary tanglegram $T$ is NP-hard \cite{FKP}, so algorithms for approximating tangle crossing numbers are needed. Let $T=(L,R,M)$ be an arbitrary tanglegram of size $n$. In this section, we present an algorithm, which produces a lower bound for $\crt(T)$ and runs in $O(n^4)$ time. \mbox{Czabarka}, Sz\'ekely, and Wagner \cite{CSW} proved that a random tanglegram with $n$ leaves has tangle crossing number $\Theta(n^2)$ with high probability. To demonstrate the strength of the lower bounds output by our algorithm, we run it on a series of tanglegrams chosen uniformly at random, finding that the lower bounds from our algorithm are approximately $0.055n^2$ which matches the ``with high probability" result of $\Omega(n^2)$ in \cite{CSW}.
% HS: This is what was written previously:
%Let $T=(L,R,M)$ be a tanglegram of size $n$. In this section, we present an algorithm which outputs a non-trivial lower bound for the tangle crossing number of $T$ in $O(n^4)$ time. As we will show, this lower bound is tight for some tanglegrams with quadratic tangle crossing number.

The algorithm runs in two phases. First it partitions the leaves of each tree into clades. In the second phase the clades are used to compute the lower bound for $\crt(T)$. Now we describe the algorithm for partitioning the leaves of a given tree into clades, given a restriction on their size. Note that we use this algorithm independently for $L$ and $R$.

\begin{algorithm}
\caption{Partition leaves into clades.}\label{alg:clade_partition}
\begin{algorithmic}[1]
\Input A binary tree $B$ and a number $C>1$.
\Output A partition of the leaves of $B$ into clades of size at most $C$.
\State Label each vertex $v$ in $B$ with the number of leaves in the clade of $B$ at $v$.
\State Let $\{v_i\}_{i=1}^k$ be the set of vertices such that the label at $v_i$ is at most $C$ and whose parent has label greater than $C$.
\State \textbf{return} $\{V_i\}_{i=1}^k$, where $V_i$ is the set of leaves in the clade of $B$ at $v_i$.
\end{algorithmic}
\end{algorithm}

Algorithm~\ref{alg:clade_partition} can be implemented in $O(n)$ time. This follows from noting that step 1 requires a post-order traversal of $B$ and each of steps 2 and 3 requires a pre-order traversal of $B$. Let $W=\{v_i\}_{i=1}^k$ be the set of vertices from step~2. Note that if $v_i,v_j\in W$, then $v_i$ is not an ancestor of $v_j$ and vice versa. It is easy to see that a consequence of this property is that the collection $\{V_i\}_{i=1}^k$ from step~3 is a partition of the leaves of $B$ into clades. Algorithm~\ref{alg:lower_bound} below computes the lower bound for the tangle crossing number.

\begin{algorithm}
\caption{Tangle crossing number lower bound.}\label{alg:lower_bound}
\begin{algorithmic}[1]
\Input Tanglegram $T=(L,R,M)$, and numbers $C_L,C_R>1$.
\Output A lower bound for $\crt(T)$.
\State Use Algorithm~\ref{alg:clade_partition} to obtain $\{U_i\}_{i=1}^\ell$ for $L$ and $C_L$.
\State Use Algorithm~\ref{alg:clade_partition} to obtain $\{V_i\}_{i=1}^r$ for $R$ and $C_R$.
\State For each $U_i$ and $V_j$, let $M_{i,j}$ be the set of matching edges with one endpoint in $U_i$ and one in $V_j$.
\State \textbf{return}
$\sum_{i_1,i_2\subseteq [\ell]}\sum_{j_1,j_2\subseteq [r]}\min\{|M_{i_1,j_1}||M_{i_2,j_2}|,|M_{i_1,j_2}||M_{i_2,j_1|}\}$
%where the sum is over $\{i_1,i_2\} \subseteq [\ell]$ and $\{j_1,j_2\} \subseteq [r]$.
\end{algorithmic}
\end{algorithm}

Note that Algorithm~\ref{alg:lower_bound} runs in $O(n^4)$. This follows since steps~1 and~2 take $O(n)$ time, step~3 takes $O(n^2)$ time, and step~4 takes $O(n^4)$ time.
 To prove correctness, suppose $U_a$ and $U_b$ are clades in $L$ and suppose $V_c$ and $V_d$ are clades in $R$. Because these are clades, any layout of $T$ will have either the $M_{ac}$
edges cross the $M_{bd}$ edges or the $M_{ad}$ edges cross the
$M_{bc}$ edges. As a result, these 4 clades will contribute at least
$\min\{|M_{ac}||M_{bd}|, |M_{ad}||M_{bc}|\}$ to the tangle crossing
number. Thus, as done in step~4, summing these minimums over all $\binom{\ell}{2}$ pairs of clades
from $L$ and $\binom{r}{2}$ pairs of clades from $R$, we obtain a
lower bound on $\crt(T)$.

One may notice that Algorithm~\ref{alg:lower_bound} depends on the choice of $C_L$ and $C_R$. When $n=k^2$, the choice of $C_L=C_R=\sqrt{n}$ is optimal for the tanglegrams in $\cT_{k^2}$ from Section~\ref{sec:onehalf} described for the proof of Theorem~\ref{th:liminf}. For each tree in these tanglegrams, Algorithm~\ref{alg:clade_partition} finds the $k$ clades with $k$ leaves that were used to build these trees. With this clade partition, $M_{i,j}=1$ for all $i,j\in [k]$. So the tangle crossing number is at least $\binom{k}{2}^2$ by Algorithm~\ref{alg:lower_bound}.  It is not hard to find tanglegrams in $\cT_{k^2}$ with tangle crossing number exactly $\binom{k}{2}^2$. Thus the output of Algorithm~\ref{alg:lower_bound} for the family of tanglegrams $\cT_{k^2}$ is tight.

We ran simulations for different choices of $C_L$ and $C_R$ with random tanglegrams drawn from a uniform distribution. Figure~\ref{fig:simulation} shows the average lower bounds when $C_L,C_R\in\{4,\sqrt{n},\frac{n}{2}\}$. For each $n\in\{10,\ldots,100\}$, we picked $100$ tanglegrams of size $n$ uniformly at random. The random sampling algorithm is a SageMath~\cite{sagemath} implementation of Algorithm~3 from~\cite[p.~253]{BKM17}. The source code for our implementation is available at~\cite{BL17}.  Based on the simulations, it appears that $C_L=C_R=\frac{n}{2}$ yields better lower bounds.

\begin{figure}[ht]
\centering
\includegraphics{avg_lower_bound.pdf}
\caption{The average lower bound for $\crt(T)$ for different choices of $C_L$ and $C_R$. The symbols \texttt{s}, \texttt{m} and \texttt{l} represent $4,\sqrt{n},$ and $n/2$ respectively. The curve labeled \texttt{ml} represents the average output with $C_L=\sqrt{n}$ and $C_R=n/2$.}
\label{fig:simulation}
\end{figure}
In \cite{CSW} it is shown that there exists $C>0$ such that a random tanglegram has tangle crossing number $C n^2$ with high probability.  Fitting the \texttt{ll} curve from Figure~\ref{fig:simulation}, the curve corresponding to $C_L=C_R=n/2$, to a quadratic function via least squares yields $0.055 n^2+O(n)$. This suggests that the tangle crossing number of the random tanglegram is at least $0.055n^2$. For the same sample, a plot of the maximum lower bounds is fit by the curve $0.08n^2 + O(n)$. These two growth rates are to be compared with the upper bound of $0.25n^2$ from Theorem~\ref{thm:limit}.

Another way to view this process is to create an auxiliary bipartite multigraph with a vertex for each clade and the number of edges between two clades is the number of edges which match a vertex of one clade to a vertex of the other clade. We then restrict to straight-line drawings where the vertices of one part remain on the line $x=0$ and the vertices of the other part lie on the line $x=1$. The minimum crossing number over all such drawings of this multigraph provides a lower bound on the crossing number of the tanglegram. However, Garey and Johnson~\cite{GJ} proved that even this problem on the auxiliary bipartite multigraph is NP-complete.


\section{Open Questions and Further Work}
Although the lower bound provided in Section 5 is tight for many small tanglegrams, we don't expect it being close to the real answer all the time, since we are doing a polynomial time approximation to an NP-hard problem.
One may notice that the lower bound is dependent on the
choice of clades. While we made an arbitrary choice, we are interested
in polynomial time algorithms to choose the clades for an optimized
lower bound.

In Section~\ref{sec:onehalf}, we provided a family of tanglegrams with
crossing number asymptotically $\frac{1}{2}\binom{n}{2}$. While the
tangle crossing number of tanglegrams in $\cT_n$ is at least
$\binom{\lfloor \sqrt{n} \rfloor}{2}^2$,
there are tanglegrams of size $n$ with larger tangle crossing
number.
Is it perhaps true that $\max\{\crt(T):T\in\cT_n\}=\gamma(n)$, at least for $n=k^2$?
We remain interested in the maximum tangle crossing
number over all tanglegrams of size $n$.

\subsection*{Acknowledgements}
The authors would like to extend their gratitude to the American
Mathematical Society for organizing the Mathematics Research Community
workshops where this work began. All authors were
supported by the National Science Foundation under Grant Number DMS
1641020. Smith
was also supported in part by NSF-DMS grant 1344199 and Sz\'ekely was also supported by the NSF-DMS grants
1300547 and 1600811.
Da Lozzo was supported by the U.S.~Defense Advanced
Research Projects Agency (DARPA) under agreement no.~AFRL
FA8750-15-2-0092.
The views expressed are those of the authors and do not reflect the
official policy or position of the Department of Defense or the
U.S.~Government. The authors would like to thank the referees for their comments to improve readability and for their suggestion of proof for Theorem~\ref{thm:tight} that did not rely on computer checks for small tanglegrams.


\bibliographystyle{plain}
\begin{thebibliography}{10}

\bibitem{BL17}
F.~Barrera-Cruz and J.~C.-H. Lin.
\newblock Code for generating tanglegrams of size $n$ uniformly.
\newblock \url{https://github.com/AMS-MRC-tanglegrams/tanglegrams}, 2017.

\bibitem{BKM17}
S.~C. Billey, M.~Konvalinka, and F.~A.~Matsen IV.
\newblock On the enumeration of tanglegrams and tangled chains.
\newblock {\em J.\ Combin.\ Theory Ser.\ A}, 146:239--263, 2017.

\bibitem{BBBN}
K.~Buchin, M.~Buchin, J.~Byrka, M.~N{\"{o}}llenburg, Y.~Okamoto, R.~Silveira,
  and A.~Wolff.
\newblock Drawing (complete) binary tanglegrams - hardness, approximation,
  fixed-parameter tractability.
\newblock {\em Algorithmica}, 62(1-2):309--332, 2012.

\bibitem{BT}
A.~Burt and R.~Trivers.
\newblock {\em Genes in Conflict: The Biology of Selfish Genetic Elements}.
\newblock {Belknap Press}, Cambridge, MA, 2008.

\bibitem{CSW}
{\'{E}}.~Czabarka, L.~A. Sz{\'{e}}kely, and S.~Wagner.
\newblock Inducibility in binary trees and crossings in random tanglegrams.
\newblock {\em SIAM J. Disc. Math.}, 31(3):1732--1750, 2017.

\bibitem{CSW2}
{\'E}va Czabarka, L{\'a}szl{\'o}~A Sz{\'e}kely, and Stephan Wagner.
\newblock A tanglegram {K}uratowski theorem.
\newblock {\em Journal of Graph Theory}, 2018.

\bibitem{sagemath}
The~Sage Developers.
\newblock {\em {S}ageMath, the {S}age {M}athematics {S}oftware {S}ystem
  ({V}ersion 8.0)}, 2017.
\newblock {\tt http://www.sagemath.org}.

\bibitem{FKP}
H.~Fernau, M.~Kaufmann, and M.~Poths.
\newblock Comparing trees via crossing minimization.
\newblock In S.~Sarukkai and S.~Sen, editors, {\em Proc. 25th Intern. Conf.
  Found. Softw. Techn. Theoret. Comput. Sci. (FSTTCS'05), LNCS vol. 3821},
  pages 457--469. Springer-Verlag, 2005.

\bibitem{GJ}
M.~R. Garey and D.~S. Johnson.
\newblock Crossing number is {NP}-complete.
\newblock {\em {SIAM} J. Alg. Disc. Meth.}, 4(3):312--316, 1983.

\bibitem{HN}
M.~S. Hafner and S.~A. Nadler.
\newblock Phylogenetic trees support the coevolution of parasites and their
  hosts.
\newblock {\em Nature}, 332:258--259, 1988.

\bibitem{HlSa}
P.~Hlin\v{e}n\'{y} and G.~Salazar.
\newblock On the crossing number of almost planar graphs.
\newblock In M.~Kaufmann and D.~Wagner, editors, {\em Graph Drawing. GD 2006.
  LNCS vol. 4372}, pages 162--173. Springer Berlin Heidelberg, 2007.

\bibitem{HT74}
J.E. Hopcroft and R.E. Tarjan.
\newblock Efficient planarity testing.
\newblock {\em J. Assoc. Comput. Mach.}, 21(4):549--568, 1974.

\bibitem{Kura}
K.~Kuratowski.
\newblock Sur le probl\`eme des courbes gauches en topologie.
\newblock {\em Fund. Math.}, 15:271--283, 1930.

\bibitem{SpT}
J.~Spencer and G.~T\'oth.
\newblock Crossing numbers of random graphs.
\newblock {\em Random Structures and Algorithms}, 21:347--358, 2002.

\end{thebibliography}

\end{document}

