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

%Changes:
%01022012: added edge crossing number
%added index
%added page numbers to bibliography
%01112012: added K11
%01282012: added HEHL12, HHL12
%03152012: added WRX11, (joint) crossing number in symbol table
%           added entry for linear crossing number (2-page) with reference to Handbook chapter for symbol
%04062012: added C12 (hardness of approximation cr)
%          added KSSH12
%04122012: added KMBW01, B09
%04142012: added note on labeled vertices, KT?
%05072012: added DEKW06
%05142012: added DV12
%05222012: added MC12
%06052012: added BEW95, BK12
%           added comment on Fary's theorem for local crossing number (and local rectilinear crossing number)
%06262012: added H16,H23, W67
%07022012: added FKP10,WSP12
%07042012: added FYX12
%07162012: added F11
%07172012: added AAFMRS12, updated dKP11 to dKP12
%           added AFI11
%07272012: added SG10 (bottleneck crossing number)
%07292012: added dKPS12
%07302012: added open question to constrained crossing number
%08302012: fixed definition of weighted crossing number (to allow reals)
%          added MS11, M08 (weighted crossing number)
%08312012: added EK01, renamed directed crossing number to upward crossing number and created separate entry
%09032012: added DW04, KT12 with a note on fixed-parameter complexity of 1-sided crossing minimization
%           fixed some minor writing issues
%09212012: added BVRK12
%10042012: added CDHK11
%           added ADLDBFR12
%           added T12
%10072012: added CG07
%10092012: added AP12?
%10162012: added dKPS12b, added multiplanar crossing numbers to index (alternative name for k-planar)
%11172012: added P12, and some more material from WSP12 on tanglegrams
%12042012: added Z12
%12052012: added H12, introduced partitioned book crossing number
%12102012: added EKWY12, mentioned airport crossing number under Orchard crossing number
%12122012: added EMKW86, BB05
%12152012: added M88
%12202012: added EL92, ELMS91, MELS95
%01032013: added wire crossing number, G89, CL98, MS95, KGB97
%01032013: added complexity of map crossing number in general
%01042013: added cyclic level crossing number (and clockwise crossing number), BBBF09, BBBH11, STT81
%01052013: added material on local crossing number (footnotes), S86, S90
%           added GS04, RS01, AR04
%01062013: added S12
%01092013: added grid crossing number, CELR97, DMS13, CK97,S90a, S10b
%01122013: added A13
%01122013: fixed definition of X(n)
%01132013: added note/pictures to simultaneous crossing number
%01222013: added A13b
%01292013: added CMG13
%03022013: added M13
%03152013: added C13 (to replace C12), updated AAFMRS12
%03212013: updated entry on geodesic crossing number (geodesic vs shortest arc)
%03222013: replaced AP12? with AP13
%---submitted to EJC
%03272013: added AAPGCHLRNU13
%04082013: added N40, B45, M34, M53, E13 with remark Forerunners of Crossing Minimization in Sociology
%04092013: added M99a, E13a
%04112013: added B51
%04122013: added C11, CS13
%03282013: added CM12, BCE13
%05072013: added FP13
%06172013: added FP13a, FM07,CH13
%06182013: added KMNT13
%06212013: added CK03
%06242013: added E86 (and added (simple) degenerate local crossing number)
%       added OTU13
%06262013: added H74
%07023024: added B70
%07092013: added FDPK13?, CRS13, BK64
%07182013: updated AAFMRS12 to AAFMRS13, updated dKPS12 to dKPS13
%08262013: added L13, W77, open question to $k$-layer crossing number
%08292013: added BES13
%09072013: added ABBGHNR13
%           added Borgatta pictures to remark on Crossing Minimization (with publisher permission: in public domain)
%10022013: added AS13, AAFMRS13a
%10312013: added CM13, removed CM12
%11092013: added AAFMRS13b, GKT13
%11192013: added FdFRV13, M91
%12012013: added S13, mentioned rectilinear local crossing number
%12062013: added CZ13, CZ14, not added: Z13 (a refinement of 1-planarity, requiring crossings to be independent or near independent)
%12072013: added SSS13, D13
%12212013: added BFK13, SSvH13
%12302013: added DV13
%01012014: added A08
%01232014: added crossing number of abstract topological graph, K91, PPST05, TT07, FPS13
%01252014: added SV93
%03042014: added DMS14 (replacing DMS13)
%03082014: added BPT06, CHS14, PT06a
%03112014: added FML14
%04122014: added SW94, W97
%04182014: extended embeddability axiom, added section on crossing lemma variants (ocr, pcr, pcr_-, iocr)
%04222014: added SSSV96a, SSSV96b
%04302014: added HVLS14
%05022014: added F03
%
%05082014: submitted version for review to EJC
%
%05122014: added SS13
%
%05122014: submitted final second version to EJC

%papers to add:
% - Rosenstiehl/Mohar: Toroidal maps, results on Fary's theorem

%things to do
% - change surface $S$ to $\Sigma$ consistently
% - in Also see and \entry make crossing numbers links to main entry
% - fix link colors so they are readable in b/w printouts
% - add symbol table?

\usepackage{amsmath, amsthm, amssymb,bm}
\usepackage{newtype}
\usepackage{verbatim}
\usepackage[hyphens]{url}
\usepackage[ocgcolorlinks=true,ps2pdf=true,pagebackref=true,breaklinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
%\usepackage[ocgcolorlinks=true,pagebackref=true,breaklinks=true]{hyperref}

\usepackage[hyphenbreaks]{breakurl}
\usepackage{supertabular}
\usepackage{wrapfig}
\usepackage{makeidx}
\usepackage{graphicx}

\usepackage{caption}
\usepackage{marginnote}

\usepackage[T1]{fontenc}

\usepackage{pstricks}
\usepackage{pst-tree}
\usepackage{pst-node}
\usepackage{pst-plot}

\usepackage{array}

\def\cro{\mathop{\rm cr}\nolimits}
\def\lcr{\mathop{\rm lcr}\nolimits}
\def\crs{\mathop{\rm crs}\nolimits}
\def\pcr{\mathop{\rm pcr}\nolimits}
\def\scr{\mathop{\rm scr}\nolimits}
\def\sgcr{\mathop{\overline{\rm scr}}\nolimits}
\def\strcr{\operatorname{\rm  str-cr}\nolimits}
\def\dcr{\mathop{\rm dcr}\nolimits}
\def\gcr{\mathop{\rm gcr}\nolimits}
\def\mcr{\mathop{\rm mcr}\nolimits}
\def\Mcr{\mathop{\rm Mcr}\nolimits}
\def\ocr{\mathop{\rm ocr}\nolimits}
\def\rcr{\mathop{\overline{\rm cr}}\nolimits}
\def\rlcr{\mathop{\overline{\rm lcr}}\nolimits}
\def\acr{\mathop{\rm acr}\nolimits}
\def\dacr{\overrightarrow{\mathop{\rm acr}\nolimits}}
\def\iacr{\mathop{\rm iacr}\nolimits}
\def\iocr{\mathop{\rm iocr}\nolimits}
\def\obf{\mathop{\rm obf}\nolimits}
\def\maxcro{\operatorname{\rm max-cr}\nolimits}
\def\maxrcr{\operatorname{{\rm max-}\rcr}\nolimits}
\def\bkcr{\mathop{\rm bkcr}\nolimits}
\def\grcr{\mathop{\rm grcr}\nolimits}
\def\tricr{\operatorname{\rm triple-cr}\nolimits}
\def\orccr{\operatorname{\rm orchard-cr}\nolimits}
\def\orcr{\overrightarrow{\mathrm{cr}}}
\def\spcr{\operatorname{\rm space-cr}\nolimits}
\def\rspcr{\operatorname{\mathrm{space-\overline{cr}}}\nolimits}
\def\ancr{\operatorname{\rm anchor-cr}\nolimits}
\def\diagcr{\mathop{\rm cr}_{\Delta}\nolimits}
\def\sfcr{\mathop{{\rm cr}_{\mathit{sf}}}\nolimits}
\def\sfocr{\mathop{\overrightarrow{\rm cr}}_{\mathit{sf}}\nolimits}
\def\ncr{\mathop{\rm ncr}\nolimits}
\def\pscr{\mathop{\widetilde{\rm cr}}\nolimits}
\def\bcr{\mathop{\rm bcr}\nolimits}
\def\ecr{\mathop{\rm ecr}\nolimits}
\def\recr{\mathop{\overline{\rm ecr}}\nolimits}
\def\maxrecr{\operatorname{{\rm max-}\recr}\nolimits}
\def\nce{\mathop{\rm nce}\nolimits}
\def\sk{\mathop{\rm sk}\nolimits}
\def\gridcr{\mathop{\overline{\rm cr}_{\#}}\nolimits}
\def\tilecr{\operatorname{\rm tile-cr}\nolimits}

%\def\PP{\mathop{N_1}}

\newcommand{\NPR}{\ensuremath{\bm{\exists \RN}}}

\def\mf{\operatorname{mon-}\nolimits\! \psi}
\def\cf{\psi}
\def\mg{\operatorname{mon-}\nolimits\! \phi}
\def\cg{\phi}

\def\mcro{\operatorname{\rm mon-cr}\nolimits}
\def\mpcr{\operatorname{\rm mon-pcr}\nolimits}
\def\mocr{\operatorname{\rm mon-ocr}\nolimits}
%\def\mrcr{\operatorname{\rm mon-rcr}\nolimits}
\def\macr{\operatorname{\rm mon-acr}\nolimits}
\def\miacr{\operatorname{\rm mon-iacr}\nolimits}
\def\miocr{\operatorname{\rm mon-iocr}\nolimits}

\def\bw{\mathop{\rm bw}\nolimits}

\def\io{\rm iocr-$0$}

\def\qer{\hfill\ensuremath{\blacklozenge}}

\newcommand{\NN}{\mathbb{N}}
\newcommand{\ZN}{\mathbb{Z}}
\newcommand{\QN}{\mathbb{Q}}
\newcommand{\RN}{\mathbb{R}}
\newcommand{\CN}{\mathbb{C}}

\newcommand{\entry}[1]{{\bfseries\noindent #1.}}

\newcommand{\mindex}[1]{\index{#1|textbf}}

\newtype{\class}{\mathbf}
\class{P}
\class{NP}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}


\def\itemi{\item [$(i)$]}
\def\itemii{\item [$(ii)$]}
\def\itemiia{\item [$(ii')$]}
\def\itemiii{\item [$(iii)$]}
\def\itemiv{\item [$(iv)$]}
\def\itemv{\item [$(v)$]}
\def\itemvi{\item [$(vi)$]}
\def\itemvii{\item [$(vii)$]}



\newtheorem{case}{Case}
\makeatletter
\@addtoreset{case}{theorem}
\makeatother

%crossing number environment
\newcounter{cnctr}[subsection]
\newcommand{\mylabel}[1]{\mbox{\textsc{#1}}\hfil}

\newenvironment{cn}[1]
{\stepcounter{cnctr}\begin{list}{}%
    {\renewcommand{\makelabel}{\mylabel}%
    \setlength{\itemsep}{-3pt}}%
    \item[{\textbf{#1}}]\nopagebreak[4]}{\end{list}}

\newcommand{\defn}{\nopagebreak[4]\item[Definition:]}
\newcommand{\reference}{\item[Reference:]}
\newcommand{\comments}{\item[Comments:]}
\newcommand{\complexity}{\item[Complexity:]}
\newcommand{\relations}{\item[Relationships:]}
\newcommand{\values}{\item[Values:]}
\newcommand{\openq}{\item[Open Questions:]}
\newcommand{\also}{\item[Also see:]}


\psset{unit=1pt}
\makeindex


\title{\bfseries The Graph Crossing Number and\\ its Variants: A Survey}
\author{
{Marcus Schaefer
} \\
{\small School of Computing} \\[-0.8ex]
{\small DePaul University} \\[-0.8ex]
{\small Chicago, Illinois 60604, USA} \\
{\small \tt mschaefer@cdm.depaul.edu}\\
}

\date{\dateline{Dec 20, 2011}{Apr 4, 2013}{Apr 17, 2013}\\
\small Revised: May 15, 2014\\
\small Mathematics Subject Classifications: 05C62, 68R10}

\begin{document}

\maketitle

\begin{abstract}
 The crossing number is a popular tool in graph drawing and visualization, but there is not really just one crossing number; there is a large family of crossing number notions of which the crossing number is the best known. We survey the rich variety of crossing number variants that have been introduced in the literature for purposes that range from studying the theoretical underpinnings of the crossing number to crossing minimization for visualization problems.
\end{abstract}

\section{So, Which Crossing Number is it?}\label{sec:WCN}

The {\em crossing number}\mindex{crossing number}, $\cro(G)$, of a graph $G$ is the smallest number of crossings required in any drawing of $G$. Or is it? According to a popular introductory textbook on combinatorics~\cite[page 40]{T06} the crossing number of a graph is ``the minimum number of pairs of crossing edges in a depiction of $G$''. So, which one is it? Is there even a difference? To start with the second question, the easy answer is: yes, obviously there is a difference, the difference between counting all crossings and counting pairs of edges that cross. But maybe these different ways of counting don't {\em make} a difference and always come out the same? That is a harder question to answer. Pach and T\'{o}th in their paper ``Which Crossing Number is it Anyway?''~\cite{PT00} coined the term {\em pair crossing number}\mindex{pair crossing number}, $\pcr$, for the crossing number in the second definition. One of the big open problems in the theory of crossing numbers is whether $\pcr(G) = \cro(G)$ for all graphs $G$. If we don't know whether they are the same, why do we see both notions called crossing number in the literature?

One potential source for the confusion between $\pcr$ and $\cro$  may be the famous crossing number inequality which states that for any graph $G$ on $n$ vertices and $m$ edges we have $\cro(G) \geq c \cdot m^3/n^2$ for $m \geq 4n$ and some constant $c$. The original proofs of this result are due independently to Ajtai, Chv\'{a}tal, Newborn, Szemeredi~\cite{ACNS82} and Leighton~\cite{L83}. However, Leighton defines $\cro$ as $\pcr$; since $\pcr(G) \leq \cro(G)$, he is making a stronger claim; his proof is analyzed in the section on crossing lemma variants below. The importance and influence of the original paper may explain why some later papers using the crossing number inequality work with the pair crossing number~\cite{A00, TV06}. The danger, of course, is that the two notions get confused; for example, Leighton~\cite[Theorem~1]{L84} proves that $\cro(G) + n \geq \Omega(\bw(G)^2)$, where $\bw(G)$ is the bisection width of $G$ (and $G$ has bounded degree); his construction is fine for the standard crossing number, but does not work for $\pcr$, the definition of crossing number he chose.\footnote{Kolman and Matousek~\cite{KM04} show that Leighton's result can be extended to $\pcr$, but with slightly weaker bounds.}


Another influential crossing number result is Garey and Johnson's proof that the crossing number problem is \NP-complete~\cite{GJ83}; Garey and Johnson first mentioned the problem as an open problem in their book on \NP-completeness, where they write: ``Open problems for other generalizations of planarity include `Does $G$ have crossing number $K$ or less, i.e.\, can $G$ be embedded in the plane with $K$ or fewer pairs of edges crossing one another?' ''~\cite[OPEN3]{GJ79}. Clearly, they are defining what we now call the pair crossing number; in their later \NP-completeness paper they write that $K$ is the least integer so that ``$G$ can be embedded in the plane so that there are no more than $K$ pair-wise intersections of curves representing edges (not counting the required intersections at common endpoints)''~\cite{GJ83}. This is already somewhat ambiguous: does ``pair-wise'' mean that they only count the pairs, or that crossings count for each pair they belong to (which is relevant if more than two edges cross in a crossing). When they show that the crossing number problem lies in \NP, it becomes clear that they mean the standard crossing number and not the pair crossing number (for which membership in \NP\ is not trivial~\cite{SSS03}).

This last example suggests another possible explanation for confusion among crossing numbers: when trying to make precise what it means to count crossings, it is natural to speak of pairwise crossings (to avoid problems with three edges crossing in the same point), and from there it is a short step to ``pairs of edges crossing''.

However, the main reason for confusion is most likely one identified by Sz{\'e}kely~\cite{S04} in his discussion of drawing conventions. In a drawing $D$ of $G$ minimizing $\cro(G)$ we have $\cro(D) = \pcr(D)$ since every pair of edges crosses at most once. This does not imply that $\pcr(G) = \cro(G)$ but it may have mistakenly suggested it; the subtle confusion is between a $\cro$-minimal drawing, in which every pair of edges crosses at most once, and a $\pcr$-minimal drawing, for which we do not know whether this is true.\footnote{Sz{\'e}kely~\cite{S04} writes: ``How is it possible that decades in research of crossing numbers passed by and no major confusion resulted from these foundational problems? The answer is the following: the conjectured optimal drawings are usually normal and nice and the lower bounds (...) usually also apply for all kinds of crossing numbers.} This confusion may have been exacerbated by the fact that $\cro(G)$ as defined above from the beginning coexisted with what we now call the {\em rectilinear crossing number}\index{rectilinear crossing number}, $\rcr(G)$, in which drawings of $G$ are restricted to straight-line drawings.\footnote{The first paper to define crossing number for arbitrary graphs also defined rectilinear crossing number~\cite{HH63}.} In a straight-line drawing $D$ of $G$ we again have $\cro(D) = \pcr(D)$ since every pair of edges can cross at most once, so it is natural to define the crossing number for straight-line drawings as the number of pairs of edges that cross in a straight-line drawing (e.g.~\cite{W70}); later authors may have dropped the straight-line requirement without changing the way crossings are counted.\footnote{Recent examples defining crossing number as $\pcr$ include textbooks in combinatorics~\cite{T06,TV06,W07}, and books in algorithms and complexity~\cite{ACGKMP99,H96,A06,AB10}.}
\begin{comment}
 Brandenburg: Nice Drawings of Graphs are Hard %(http://books.google.com/books?id=kOU5wrsqvcgC&pg=PA8),
\end{comment}

\begin{remark}
As far as we know there are currently only three crossing number variants for which it is known that counting pairs of crossings as opposed to all crossings decreases the value of the crossing number: the constrained crossing number~\cite{MZ99}, the local crossing number (see that entry), and the geodesic crossing number (on a pseudosurface, see Footnote~\ref{foot:pcrvscr}).
\qer \end{remark}

\subsection*{Adjacent Crossings}

There is some independent corroboration to Sz{\'e}kely's thesis that $\cro$-minimal drawings are at the root of the confusion between different crossing number notions; $\cro$-minimal drawings also have the property that adjacent edges do not cross, and sure enough there are several instances in which researchers have ignored (sometimes at their peril) crossings between adjacent edges. Tutte, in a slightly different context, famously remarked that ``adjacent crossings are trivial and easily got rid of''~\cite{T70}.

To show that adjacent edges do not cross in a $\cro$-minimal drawing, one typically refers to two pictures, like the left and middle pictures of Figure~\ref{fig:adcross}.
\begin{figure}[htb]
\begin{center}
\begin{tabular}{cp{0.1in}cp{0.1in}c}
\begin{pspicture}(10,0)(90,110)

\pscurve(20,90)(70,30)(50,0)(30,30)(80,90)

\cnode*(50,0){2pt}{v0}
\cnode*(20,90){2pt}{v1}
\cnode*(80,90){2pt}{v2}
\end{pspicture}
&&
\begin{pspicture}(10,0)(90,110)

\pscurve(20,90)(70,30)(50,0)(30,30)(80,90)
\pscircle*[linecolor=white](50,64){4}
\psarc(43.25,64.3){4.9}{-45}{45}
\psarc(56.75,64.3){4.9}{135}{-135}

\cnode*(50,0){2pt}{v0}
\cnode*(20,90){2pt}{v1}
\cnode*(80,90){2pt}{v2}
\end{pspicture}
&&
\begin{pspicture}(0,0)(100,110)

\pscurve(20,90)(70,30)(50,0)(30,30)(80,90)

\cnode*(50,0){2pt}{v0}
\cnode*(20,90){2pt}{v1}
\cnode*(80,90){2pt}{v2}

\cnode*(50,30){2pt}{v3}
\cnode*(75,65){2pt}{v4}
\cnode*(25,65){2pt}{v5}

\nccurve[linecolor=gray,angleA=140,angleB=135,ncurv=5]{v3}{v4}
\nccurve[linecolor=gray,angleA=40,angleB=45,ncurv=5]{v3}{v5}
\end{pspicture}

\end{tabular}
\end{center}
\caption{{\em (left)} adjacent crossing, ({\em middle}) removing adjacent crossing, ({\em right}) adjacent crossing that's hard to remove by local redrawing.}\label{fig:adcross}
\end{figure}

While this works fine for the standard crossing number (though even there one needs an additional argument that shows how to remove self-crossings that can be introduced when swapping arcs), this need not be the case for other crossing number notions. For example, consider the pair crossing number\index{pair crossing number} in the scenario depicted in the right picture of Figure~\ref{fig:adcross}; swapping the arcs, or even just rerouting one of the arcs along the adjacent edge will lead to an increase in the pair crossing number, so the simple local redrawing moves common for $\cro$ do not seem to work. It is open whether a $\pcr$-minimal drawing may have crossings between adjacent edges (this question is equivalent to whether $\pcr < \pcr_+$, see the entry on pair crossing number in Section~\ref{sec:C}).

Even for the standard crossing number\index{crossing number} this is not the end of the story for adjacent crossings. Here is a quote from a recent paper on Albertson's conjecture: if $G$ has chromatic number at least $r$, then $\cro(G) \geq \cro(K_r)$.

\begin{quote}
``A crossing of two edges $e$ and $f$ is {\em trivial} if $e$ and $f$ are adjacent or equal, and it is {\em non-trivial} otherwise.
A drawing is {\em good} if it has no trivial crossings. The following is a well-known easy lemma.

{\bfseries Lemma 1.1.} A drawing of a graph can be modified to eliminate all of its trivial crossings,
with the number of non-trivial crossings remaining the same.''~\cite{OZ09}
\end{quote}

The {\em independent crossing number}\mindex{independent crossing number}, $\cro_-(G)$, only counts crossings occurring between independent edges. If Lemma~1.1 were true, it would imply that $\cro_- = \cro$, a question that's open to the best of our knowledge.\footnote{Start with a $\cro_-$-minimal drawing. By the lemma, all trivial crossings can be eliminated, only leaving ``non-trivial'' crossings, that is, crossings that count towards $\cro$, so $\cro$ of the resulting drawing is at most $\cro_-$. In the other direction, $\cro_- \leq \cro$ follows from the definition.} Fortunately, the use of Lemma~1.1 could be eliminated in this case~\cite{O13}, but wouldn't it be nice if we could establish $\cro_- = \cro$ and not have to worry about adjacent crossings anymore? The left and middle picture of Figure~\ref{fig:adcross} explain why Lemma~1.1 looks so convincing: crossings between adjacent edges can easily be removed by local redrawing, but the right picture shows that this can create crossings between non-adjacent pairs of edges. A proof of a result like Lemma 1.1 will require a more global approach.

\begin{question}\label{que:adcross}
Here are two simple-looking problems that illustrate our lack of understanding of adjacent crossings. $(i)$ Can subdividing an edge change $\cro_-$ of a graph? $(ii)$ Suppose a graph can be drawn on a surface so that all crossings in the drawing are between adjacent edges. Can the graph be embedded in that surface? An answer to the second question is known for the plane and the projective plane by virtue of the Hanani-Tutte theorems for those surfaces~\cite{PSS09c}, but not for any other surface. The first question is open.
\end{question}

While not nearly as common as the $\pcr$ versus $\cro$ problem, $\cro$ is occasionally defined as the smallest number of independent crossings; this may again be due to the fact that for straight-line drawings, adjacent edges do not cross. For example, Moon~\cite{M65} in one of the earliest papers on crossing numbers defines what amounts to the independent (geodesic) spherical crossing number\index{independent spherical crossing number} which equals the geodesic spherical crossing number\index{spherical crossing number}, since geodesics representing adjacent edges do not cross on the sphere. Nahas~\cite{N03} defines the crossing number of $K_{m,n}$ as $\cro_-(K_{m,n})$\index{independent crossing number}. Papers on crossing minimization via linear programming also often ignore variables that encode crossings between adjacent edges. This is fine, of course, as the resulting program enforce that adjacent edges do not cross; otherwise, they would compute $\cro_-$.

\begin{remark}
As far as we know there are only two crossing number notions for which the independent variant is known to differ from the regular variant, namely the odd\index{odd crossing number} and the algebraic\index{algebraic crossing number} crossing number: there are graphs $G$ for which $\iocr(G) < \ocr(G)$ and $\iacr(G) < \acr(G)$~\cite{FPSS12b}. The same paper also shows that prohibiting crossings between adjacent edges in monotone drawings can lead to an increase in the monotone odd crossing number\index{monotone odd crossing number}. The same is true for the local crossing number\index{local crossing number}, see Footnotes~\ref{foot:localdiff} and~\ref{foot:localeq}, and the simultaneous crossing number\index{simultaneous crossing number}, see Footnote~\ref{foot:scrad}. For directed graphs, the bimodal crossing number\index{bimodal crossing number} may require crossings between adjacent edges in an optimal drawing.
\qer \end{remark}

\subsection*{Crossing Lemma Variants}

The crossing lemma, or crossing number inequality, established independently by Ajtai, Chv\'{a}tal, Newborn, Szemeredi~\cite{ACNS82} and Leighton~\cite{L83}, is one of the most celebrated (and famous) results on crossing numbers.\footnote{For a very readable introduction, see Terence Tao's blog enty~\cite{T07a}, which also discusses applications to incidence geometry and sum-product estimates.} In its original form, it shows that $\cro(G) \geq c \cdot m^3/n^2$, where $n = |V|$, and $m = |E|$. How does it fare for other crossing number variants, and pair and odd crossing number in particular? Crossing lemmas for other variants are listed in the compendium below.

The usual probabilistic proof of the crossing lemma for a crossing number $\gamma$ proceeds in three steps: first, we observe that if $\gamma(G) = 0$, then $G$ is planar, so Euler's formula applies, and $m \leq 3n-6$, where $n = |V(G)|$, $m = |E(G)|$. In a second step, we argue that we can remove at most $\gamma(G)$ edges from $G$ to reduce $\gamma$ to $0$, so $m-\gamma(G) \leq 3n-6$, and, hence, $\gamma(G) \geq m-3n$. In a third step, we consider a random subgraph $G'$ of $G$, keeping each vertex with probability $p$. The expected number of vertices and edges in $G' = (V',E')$ are $\mathbb{E}(|V'|) = pn$
and $\mathbb{E}(|E'|) = p^2n$. Fix a $\gamma$-minimal drawing $D$ of $G$. Assuming each crossing in $D$ which contributes to $\gamma$ is caused by two independent edges, a crossing is associated with four endpoints. For the crossing to survive in $D'$, the induced drawing of $G'$, all four endpoints have to be kept, so $\mathbb{E}(\gamma(G')) \leq p^4 \gamma(G)$.  Now
$G'$ fulfills $\gamma(G') \geq |E'| - 3|V'|$ (by the second step), so, taking expected values, we get $p^4 \gamma(G) \geq p^2m-pn$, or $\gamma(G) \geq mp^{-2} - np^{-3}$ (assuming $p \geq 0$). Choosing $p = 4n/m$ implies that $\gamma(G) \geq 1/64 m^3/n^2$, as long as $m \geq 4n$ (which we need so $p \leq 1$).

For $\gamma = \cro$, this proof works just fine, and it's been claimed in the literature (e.g.\ \cite{PRTT06}) that this proof also works for pair and odd crossing numbers. But there are two subtle problems, and none of the published proofs avoid both. Consider the case $\gamma = \pcr$\index{pair crossing number}, the case claimed by Leighton~\cite{L83}: in the second step, the $\pcr$-minimal drawing $D$ may contain crossings between dependent edges, and those contribute to $\pcr$. Since we do not know how to remove dependent crossings in general without increasing $\pcr(D)$, we have to take dependent crossings into account; since those survive with probability $p^3$, we would get a substantially worse bound than $\Omega(m^3/n^2)$ on $\pcr(G)$. Alon~\cite{A00}, and Tao and Vu in their book on additive combinatorics~\cite{TV06} circumvent this problem by working with $\pcr_-$, the independent pair crossing number\index{independent pair crossing number}, in which only the number of crossings of independent pairs of edges are counted. However, for that crossing number the second step is no longer obvious: if we have a drawing $D$ with $k$ independent pairs of edges crossing, then removing $k$ edges yields a drawing in which all remaining crossings are dependent. Is that graph planar? The answer is yes, but it requires the Hanani-Tutte theorem to prove so (at least we are not aware of a direct proof).

\begin{remark}
 Since the Hanani-Tutte theorem is not known to be true for the torus, this means that we do not currently have a proof of the crossing lemma for $\pcr$ or $\pcr_-$ on the torus. A positive answer to Question~\ref{que:adcross}\ $(ii)$ would be sufficient to settle the problem. For the standard crossing number, extensions of the crossing lemma to arbitrary surfaces are known~\cite{SSSV96b}.
\qer \end{remark}

Pach and T\'{o}th~\cite{PT00} work with $\gamma = \ocr$, the odd crossing number\index{odd crossing number}, which only counts pairs of edges crossing an odd number of times. They use Hanani-Tutte in the first and second steps, but in the third step again assume that a crossing is associated with four endpoints, which may not be the case for $\ocr$. However, their proof is essentially correct if read for $\gamma = \iocr$, the independent odd crossing number\index{independent odd crossing number}, which counts the number of independent pairs of edges crossing an odd number of times. For $\iocr$, the Hanani-Tutte theorem guarantees that we can remove $\iocr(G)$ edges from $G$ to make $G$ planar, ensuring the correctness of the first and second steps. And since $\iocr$ {\em by definition} only counts independent pairs, the argument in the third step also works. We conclude that $\iocr(G) \geq 1/64 m^3/n^2$, as long as $m \geq 4n$. Since $\ocr$, $\pcr$, and $\pcr_-$ (as well as $\acr$ and $\iacr$) are all bounded below by $\iocr$, this immediately proves the crossing lemma for all these variants. The constant $c = 1/64$ in these cases is weaker than what is currently known for $\cro$, but seems hard to improve~\cite[Remark~4.2]{PRTT06}.

\subsection*{Conclusion}

We are forewarned that there is some subtlety to defining the crossing number, but rather than seeing this as an issue, this gives us an opportunity. J\'{a}nos Pach once said, in effect, ``we don't need more crossing numbers, we need fewer crossing numbers''. As a look at the compendium will show it may be too late for that. Some crossing number variants may have arisen by mistake, but most were defined with a specific purpose in mind. This purpose may be theoretical, aimed at developing a theory of crossing number (as Tutte~\cite{T70} did with his crossing chains and $\iacr$) or
it may be practical, aimed at improving the layout of graphs (as in the Metro-line crossing minimization problem). The recent growth of graph drawing research and crossing minimization problems for very specific visualization tasks  is important evidence for that. Some variants, such as the local crossing number\index{local crossing number} or the maximum rectilinear crossing number\index{maximum rectilinear crossing number}, are so fundamental that they have been rediscovered over and over again under various names.

This survey of crossing number variants follows two main goals: to collect as many different types of crossing number variants from the literature as possible (unifying presentations and names), and to attempt a systematic description of what makes a crossing number. The results of this second step are presented first, in Section~\ref{sec:ASA}. The results of the first step are collected in the Compendium in Section~\ref{sec:C}. Originally, the paper was to contain a section on the history of the crossing number, however, Beineke and Wilson's recent ``Early History of the Brick Factory problem''~\cite{BW10} has made this part mostly superfluous.

\begin{remark}[Forerunners of Crossing Minimization in Sociology]\label{rem:FCMS}
David Eppstein~\cite{E13} recently discovered the earliest known references to (general) crossing minimization\footnote{There are earlier references to crossing minimization when it comes to specific families of graphs~\cite{C1889, K1889, S1893}, but none that are as general as these.}. They come from sociology, more specifically the area of sociometry which is concerned with measuring (and depicting) social relationships: in discussing sociograms (essentially graphs), Bronfenbrenner~\cite{B45} in $1945$ writes that ``The arrangement of subjects on the diagram, while haphazard in part, is determined largely by trial and error with the aim of minimizing the number of intersecting lines''. Sociograms were introduced in J.L. Moreno's ``Who Shall Survive''~\cite{M34} in 1934, however, the first edition of that book, while containing many interesting graph visualizations, does not seem to discuss crossing minimization. In the later, 1953, edition~\cite{M53}\footnote{This edition is available online at \url{http://www.asgpp.org/docs/WSS/wss\%20index/wss\%20index.html}}, there is an interesting paragraph which reads: ``A readable sociogram is a good sociogram. To be readable, the number of lines crossing must be minimized.'' This mantra occurs repeatedly in the literature on sociograms, and at least once in an earlier paper by Borgatta~\cite{B51} who writes: ``A readable diagram is a good diagram. To be readable, the number of lines crossing must be minimized. This may be taken as a primary principle in the construction of inter-action diagrams; the fewer the number of lines crossing, the better the diagram. The problem, then, is to find the procedure which best minimizes the number of lines that cross in a diagram.'' Borgatta then outlines a multi-stage heuristic for crossing minimization (start with a small number of high-degree vertices, drawn far apart, add vertices by decreasing degree, redraw diagram to improve drawings of subgroups), and illustrates his method by working out an example on $26$ vertices and $43$ edges, shown in Figure~\ref{fig:Borg}; his final drawing uses two crossings (which is optimal, since his graph contains two disjoint copies of $K_5$).
\begin{figure}[htb]
\begin{center}
\begin{tabular}{ccc}
%\includegraphics[width=2.5in, natwidth = 709px, natheight = 1026px]{BorgattaDiagram1.png}
\includegraphics[width=2.5in]{BorgattaDiagram1.eps}
&&
%\includegraphics[width=2.6in, natwidth = 702px, natheight = 975px]{BorgattaDiagram3.png} \\
\includegraphics[width=2.6in]{BorgattaDiagram3.eps} \\
$(a)$ && $(b)$
\end{tabular}
\end{center}
\caption{Maybe the first published instance of a crossing minimization, reducing $16$ crossings in $(a)$ to the optimal $2$ crossings in $(b)$. Taken (with permission) from a 1951 article in the journal ``Group Psychotherapy'' by Edgar F. Borgatta~\cite{B51}.}\label{fig:Borg}
\end{figure}

 The earliest reference (found so far) on crossing minimization seems to be a 1940 paper by Northway~\cite{N40} in which she suggests the use of radial layouts; vertices (school children) are placed at various distances from a center based on some quantity (their scores); directed edges between them are drawn as straight-line arrows. She writes that ``it has been convenient to use counters [...]. These are moved in the circles to which their score belongs and arranged to get the best "fit" among the individuals, i.e., to have as few long lines and crossing lines as possible.'' She also suggests that grouping vertices by some characteristic (in her example, sex), simplifies this task. These quotes are quite remarkable, and one wonders whether there is more early material on crossing minimization that is unknown in the mathematical literature.
\qer \end{remark}

One aspect that remains to be studied, is the history of knot crossing numbers and their influence (or not) on graph crossing numbers. When it comes to methods of counting crossings, it seems that knot crossing numbers led the way; e.g.\ Tutte's theory of crossing numbers is based on counting crossings algebraically, as one would for the algebraic crossing number in knot theory, and as Gau{\ss} would have done hundreds of years ago~\cite[page 271--279]{G00}.

\begin{remark}[Axioms]
  What makes a crossing number a crossing number? We have chosen a descriptive/extensional approach for this paper, however, the material collected here may at some point make a basis for a prescriptive/intensional approach. As far as we know there has never been an attempt to axiomatize the notion of crossing number, either as the standard crossing number or as the family of crossing number variants. Although not plentiful, there are some candidate axioms based on common crossing number properties.
  \begin{description}
  \item[Embeddability] Crossing numbers are generally considered to be ``measures of non-planarity'' or non-embeddability. It seems natural then to require that if $\gamma_{\Sigma}(G) = 0$ for some crossing number $\gamma$ in surface $\Sigma$, then $G$ is embeddable in $\Sigma$. Let us call this the {\em embeddability axiom}. For the standard crossing number\index{crossing number} this is true by definition (on any surface). For the independent odd crossing number\index{independent odd crossing number} it amounts to the Hanani-Tutte theorem (which is only known for the plane and the projective plane). For the confluent crossing number\index{confluent crossing number} and the string crossing number\index{string crossing number}, the embeddability axiom fails (complete graphs have confluent embeddings and there are non-planar string graphs). A stronger, quantitative version of this axiom would require that the removal of at most
      $\gamma(G)$ edges from $G$ makes $G$ planar. The intuition behind this strengthened version is that each crossing
      is caused by two edges, so a crossing can be eliminated by removing one of the participating edges. This axiom holds
      for the standard crossing number\index{crossing number} by definition (on any surface), and for the pair crossing number\index{pair crossing number} and independent odd crossing number\index{independent odd crossing number} by the Hanani-Tutte theorem. It fails for the degenerate crossing number\index{degenerate crossing number}, in which more than two edges can cross in a crossing, and for any of the crossing numbers based on maximization.
  \item[Embedding] By the same ``measure of non-planarity'' argument, a graph $G$ that can be embedded in a surface $\Sigma$ should have crossing number $\gamma_{\Sigma}(G) = 0$. Let us call this the {\em embedding axiom}. This axiom is trivially true for most crossing number variants, although there are some notable exceptions including crossing numbers defined via maximization (maximum crossing number\index{maximum crossing number}, maximum rectilinear crossing number\index{maximum rectilinear crossing number}) and crossing numbers that require certain drawing conventions (e.g.\ bimodal\index{bimodal crossing number}, bipartite\index{bipartite crossing number}, convex\index{convex crossing number}, and orchard crossing numbers\index{orchard crossing number}). For the rectilinear crossing number\index{rectilinear crossing number}, the axiom amounts to Fary's (or Wagner's or Steinitz's) theorem.
      It appears to be an open problem whether the axiom holds for the geodesic crossing number\index{geodesic crossing number} on other surfaces.\footnote{An announcement of a solution in~\cite[page 312]{T95a} may have been
      in error~\cite{T11}.}
  \item[Subgraph Monotonicity] The {\em subgraph monotonicity axiom} requires that if $G$ is a subgraph of $H$, then $\gamma(G) \leq \gamma(H)$. This is true (and trivial) for nearly all crossing number variants. We are aware of only two provable exceptions, the triple crossing number\index{triple crossing number}, for which $\tricr(K_{5,3}) = \infty$ while $\tricr(K_{6,3}) = 2$~\cite{TT10}, and the confluent crossing number\index{confluent crossing number} (all complete graphs have confluent crossing number $0$). For the maximum crossing number\index{maximum crossing number}, monotonicity is a well-known open problem even if $G$ is required to be an induced subgraph of $H$~\cite{RSP91}. A stronger requirement is
      {\em topological minor monotonicity}: if $G$ is a subdivision of a subgraph of $H$, then $\gamma(G) \leq \gamma(H)$. This is still true for a large number of crossing numbers, but is not known to hold for any of the independent crossing number variants, like $\cro_-$\index{independent crossing number}, and typically fails for alternative representations (like the confluent crossing number\index{confluent crossing number}). In contrast, most crossing numbers do {\em not} satisfy {\em minor-monotonicity} which has led to the definition of the minor (or minor-monotone)\index{minor crossing number} and the genus crossing numbers\index{genus crossing number}.
  \item[Surface Monotonicity] The {\em surface monotonicity axiom} requires that if surface $\Sigma$ has smaller genus than surface $\Gamma$, then $\gamma_{\Sigma} \geq \gamma_{\Gamma}$. We are not aware of any crossing number that does not fulfill this axiom. One could imagine sharper quantitative versions of this axiom, for example if $\Sigma$ has smaller genus than $\Gamma$, then $\gamma_{\Sigma}(G) > \gamma_{\Gamma}(G)$ unless $\gamma_{\Sigma}(G) = 0$.
  \end{description}
  One can imagine further axioms, for example based on what may be called the {\em spectrum} of the crossing number of a graph $G$: $\{\gamma(D): D $ is a drawing of $G\}$. This notion has occasionally been studied, e.g.~\cite{FK76,PRS91} for the maximum crossing number\index{maximum crossing number}. Harborth~\cite{H02} showed that the spectrum of $K_{14}$ under $\cro$ is not a subset of the spectrum of $K_{14}$ under the $2$-page crossing number $\bkcr_2$\index{book crossing number}, and conjectured that $K_{14}$ is the smallest complete graph for which the spectra of $\cro$ and $\bkcr_2$ differ.\footnote{Harborth mentions an unpublished paper that seems to establish significant parts of this conjecture.}

  It is probably unreasonable to expect an axiomatization of the (standard) crossing number\index{standard crossing number}; however, it may be reasonable to
  attempt to axiomatize sufficiently many standard properties of the crossing number that would show why many of them
  allow a crossing lemma. Or why many of them can be bounded within each other.
\qer \end{remark}

\section{A Systematic Approach}\label{sec:ASA}

In this section we want to take a systematic approach to crossing number variants.
The discussion is based on the crossing number notions collected from the literature and presented
in Section~\ref{sec:C}, and the reader is asked to look for definitions there if they are not given in this section. Before reviewing crossing numbers, we begin with a discussion of crossings themselves.

What is a crossing? Typically, a crossing is defined to be a common interior point of two edges; hence, a shared endpoint (of two adjacent edges) is not considered a crossing. This distinguishes a crossing from an intersection of two edges.\footnote{One subtlety already: it excludes from the notion of crossing any intersection occurring when an edge passes {\em through} a vertex, as opposed to ending there. Such intersections are typically prohibited, but what happens if we allow them?}

The definition as given also distinguishes a crossing from the point in the plane at which the crossing occurs (and this is good). The definition does, however, include points in which two curves touch; this is of no consequence for the standard crossing number\index{crossing number} since in crossing-minimal drawings no touching points occur, but for other variants, e.g.\ the odd crossing number\index{odd crossing number}, counting touching points as crossings would trivialize the notion. For Kleitman~\cite{K70} a crossing requires that the two edges involve actually cross. This requirement leads to other issues if not handled carefully: take a drawing of $K_5$ with a single crossing and replace the crossing with a short line segment (so the two edges involved in the crossing run parallel for a short stretch). According to Kleitman's definition this drawing is free of crossings (even though it has an infinite number of intersection points). This suggests the importance of restricting drawings to drawings with a finite number of intersection points (which is what we will do) which causes a slight inconvenience when dealing with confluent drawings: in confluent drawings of graphs edges seem to overlap heavily. We resolve this by looking at confluent drawings not as drawings of the edges and vertices of the graph, but as a drawing of branches and switches that represent the underlying graph.

We return to a more formal definition of crossing in Section~\ref{sec:TB} after discussing basic drawing conventions.

\begin{figure}[htb]
\begin{center}
\includegraphics[width=3in]{VeraCruzK8.eps}
\end{center}
\caption{Drawing of $K_8$ from de la Vera Cruz' {\em Recognitio Summularum} with ribbons crossing through each other. The image is taken from the online (public domain) version of the book available through Primeros Libros at \url{http://www.primeroslibros.org/browse.html}. Page $36$ contains the drawing of $K_8$, page $57$ contains a drawing of $K_{4,4}-e$.}\label{fig:VCK8}
\end{figure}

\begin{remark}[Drawing Crossings]\label{rem:DC}
  How do we draw a crossing? The most common way is to simply let the curves representing the edges cross, preferably at a large angle (RAC drawings require right angles); alternatively one can draw crossings as bridges or by using edge casing; see ``Edges and switches, tunnels and bridges'' by Eppstein, van Kreveld, Mumford and Speckmann~\cite{EvKMS09}. There may be more options in alternative styles; for example, if vertices are represented by disks and edges as ribbons with boundary, then crossings can be visualized by ribbons passing above or below each other, see for example the 16th century drawing of $K_{12}$ in~\cite[Figure~6]{KMBW01} which has both vertex and edge labels (illustrating a modal square of opposition). Alonso de la Vera Cruz uses an interesting twist to visualize $K_{8}$ (in his 1554 {\em Recognitio Summularum}, again for a square of opposition). He not only has ribbons passing above and below each other, but also through each other, see Figure~\ref{fig:VCK8}; for background on the book, see~\cite{B09}.
\qer \end{remark}



  Most of the research on crossing numbers seems to have been done in English, but there are terms for crossings and crossing numbers in other languages. In German there is {\em Kreuzung}, {\em Schnitt} and {\em Doppelpunkt} for crossing and {\em Kreuzungszahl} for crossing number.\footnote{Steinitz~\cite{S23} uses the term Doppelpunkt; it stems from the algebraic tradition and is now used for crossings in knots. {\em Schnittzahl} typically means intersection number from algebraic geometry rather than crossing number.} In French, we have {\em points d'intersection}~\cite{U55} and {\em croisement} for crossings\footnote{Leclerc and Monjardet~\cite{LM69} use {\em points non signifiants} (as opposed to the points representing vertices).} and {\em nombres de croisement} for crossing number. In Italian there is {\em incrocio} for crossing and {\em numero d'incrocio} for crossing number.

\subsection{A General Notion of Crossing Number}

There are (at least) three main dimensions which influence the specific notion of crossing number one ends up with: the {\em drawing style}, the {\em method of counting}, and the {\em mode of representation}. Within each dimension multiple decisions can be made, both global and local. Global decisions in the drawing style include: underlying surface, straight-line edges, monotone edges, local decisions include: no three edges sharing the same interior point, no edge passing through a vertex; for method of counting, again we have global decisions such as: do we count crossings between adjacent edges or edges that cross evenly and local decisions: each crossing counts $1$ or $\pm 1$ (depending on orientation), etc.; mode of representation is typically global; in the standard mode a curve carries exactly one edge, but there are alternative models like confluent graph drawing and simultaneous graph drawing in which a curve can carry more than one edge.

Many of these decisions have rarely been made explicitly; they were either assumed implicitly or not considered at all. Even as one surveys the surprisingly large collection of different crossing number variants that exist, one often finds that they differ from the standard crossing number in at most one of the three dimensions (although there are some exceptions such as the local toroidal crossing number\index{local toroidal crossing number}, the book edge crossing number\index{book edge crossing number}, or the monotone independent odd crossing number\index{monotone independent odd crossing number}).

Within this framework we can attempt a general definition of a crossing number $\psi$: given a graph $G$ consider a particular drawing $D$ representing $G$ (via some mode of representation). Assign to each crossing in $D$ a value (typically $1$, but could be $-1$, e.g.\ for algebraic crossing number\index{algebraic crossing number}; values in $\QN$, $\CN$ or some group may be interesting). Now calculate the crossing number $\psi(e,f)$ for each pair of edges.\footnote{One can also define the crossing number by counting crossings along each edge (and dividing the total by $2$) but pairwise counting is the standard. This would seem to exclude some variants, like the local crossing number\index{local crossing number} or the triple crossing number\index{triple crossing number}, but see the discussion in Example~\ref{ex:cndef}.} This is typically done as the sum (or absolute sum) of the values of the crossings shared by $e$ and $f$.\footnote{One could consider multiplication or maximization instead of addition.} Finally, $\psi(D)$ is calculated by combining all the values of $\psi(e,f)$, typically by summing them up (over all unordered pairs). Then $\psi(G)$ is the minimum (sometimes maximum) over all $\psi(D)$ where $D$ is an admissible drawing (depending on the drawing style) that represents $G$. This generic definition of crossing number describes nearly all crossing number variants reviewed in this paper. In any case, we are trying to be descriptive, not prescriptive.

\begin{example}\label{ex:cndef}
Let us check some of the crossing number variants to test the bounds of our general crossing number notion. For definitions, see the compendium.
\begin{description}
 \item[Natural fits.]  The degenerate crossing number\index{degenerate crossing number} fits the general definition above: a crossing shared by $k$ edges is weighted as $1/{k \choose 2}$. Independent crossing numbers\index{independent crossing number} can be captured by assigning values of $0$ to crossings between adjacent edges. The Rule $+$ variants introduced  by Pach and T\'{o}th~\cite{PT00b} are captured in the drawing style: adjacent edges are not allowed to cross (alternatively, we could assign a value of $\infty$ to each adjacent crossing). The triple crossing number\index{triple crossing number} (in which all crossings have to be triple crossings) can be captured by pairwise counts (each triple crossings gives three double crossings; since only triple crossings are allowed we can divide by $3$ to get the triple crossing number). The pair crossing number\index{pair crossing number} maximizes (rather than adds) the number of crossings along each pair of edges.
 \item[Acceptable fits.] The local crossing number\index{local crossing number} would be a more natural fit for counting crossings edge-wise (as opposed to pairwise), but it can be made to fit the general definition. It is expressible as $\max_{e \in E} \sum_{f \in E} \cro(e,f)$.
 \item[Forced fits.]  The minor crossing number\index{minor crossing number} can be made to fit the general description of crossing number above, albeit with some force: say a drawing $D$ represents $G$ if $D$ is a drawing of a graph containing $G$ as a minor. One could question whether this is a natural interpretation, but we decided to include this notion.
 \item[Not a fit.] The {\em skewness}\index{skewness} of a graph, the smallest number of edges that need to be removed from a graph to make it planar, does not fit the general definition of crossing number given above. One can debate whether skewness is a crossing number variant, but we decided to exclude it. It is easy to abbreviate the standard definition of crossing number to the point where it incorrectly defines a notion similar to skewness, e.g.\ ``Is the crossing number of $G \leq K$? i.e. can $G$ be embedded in the plane in such a way that no more than $K$ edges cross?''~\cite{H98w}, see the {\em edge crossing number}\index{edge crossing number}. Another notion that is not covered by the general description is the {\em nodal crossing number}\index{nodal crossing number} which is similar to the local crossing number, but looks at the total number of crossings with any edge incident to a vertex, and then maximizes over all vertices. One could think of it as a local crossing number for hypergraphs.\index{hypergraph crossing numbers} Even though it does not fit our general model, we decided to include it because of its ties to the local crossing number.
\end{description}
\end{example}

Let us next review some of the options available for creating a crossing number within the three dimensions we identified; we start with a discussion of drawing styles, followed by methods of counting, and modes of representation.

\subsection{Drawing Styles}

In this section we discuss different drawing styles; we make a rather rough distinction between basic drawing properties that are often taken to be part of the very definition of a drawing, sometimes called a good drawing and what may more properly be called a style of drawing (Section~\ref{sec:SoD}). We treat drawing surfaces separately in Section~\ref{sec:DS}.

\subsubsection{The Basics}\label{sec:TB}

A drawing stripped of any mystic ballast is just a mapping of a graph (vertices and edges) to a surface. With this generous definition of drawing, the whole graph could map to a single point, losing all structure. There has not been much discussion of what assumptions to make on a drawing, Eggleton's thesis~\cite{E73} is one of the rare places in which some of these issues are brought up. We first discuss issues related to drawing {\bfseries vertices and edges}.

\begin{description}
  \item[An edge is represented by a curve.] But what type of curves do we allow? Do we want a curve to be connected? In the work on odd and algebraic crossing numbers edges are often split into multiple components temporarily. Becker, Eick and Wilks~\cite{BEW95} suggested ``line shortening'' for geometric drawings: only the ends of edges are drawn (without further restrictions this removes all crossings, see~\cite{BK12} for a recent paper). If we require the curve to be connected (but not path-connected), we can get some anomalies, for example Kratochv{\'{\i}}l~\cite{K91} notes that every graph is a string graph if strings are allowed to be arbitrary connected curves (string graphs are intersection graphs of simple curves in the plane). So we should require edges to be simple plane curves, which are homeomorphic images of the unit interval. This is the typical choice when defining a drawing. However, it does preclude edges from crossing themselves which may be desirable in some contexts. We discuss the issue of self-intersections below. For practical reasons, it may make sense to ``fatten up'' edges, we discuss this possibility below together with vertex representations.
  \item[Vertices are endpoints of the edge.] Often edges are defined as open arcs at which point one has to specify that the points representing the vertices of the edge occur at (opposite) ends of the arc. One could easily imagine a drawing of $K_5$ with the $5$ endpoints as isolated points and $10$ parallel arcs representing the edges (maybe with the ends of the arcs labeled by the names of the vertices). One could also consider this a special case of allowing a vertex to be represented by multiple points (see below).
  \item[Vertices are represented by points.] Suppose we represent vertices by disks and only require edges to attach at the boundary of the disk. This idea was (ab)used by Dudeney in his original solution to the Gas, Water, Electricity problem~\cite[Problem 251]{D59} which essentially asks for a crossing-free drawing of $K_{3,3}$: Dudeney has the final path---which would cause a crossing---pass through one of the houses (vertices) which he drew as rectangles. Suppose we do allow edges to pass through vertices. If we allow such crossings for free (as Dudeney suggests) we trivialize the notion of crossing number: every graph can be represented so that a vertex is a disk, edges end on the boundary of the disk representing their endpoint, edges are allowed to pass through the disk, and no two edges cross. However, we could consider allowing edges to pass through vertices for a cost. As far as we know no such notion has been investigated, although there are crossing numbers which count crossings other than edge crossings (e.g.\ the spine crossing number\index{spine crossing number}).

      One reason to relax the requirement that vertices be points may be that the vertices represent objects with internal structure that has to be captured. Eades and Lai~\cite{EL92,LE02} called these {\em practical graphs}, and suggested a two-step approach: first use a general layout algorithm for the abstract graph, and then, in a second step, lay out the graph with vertices having various shapes; the goal of the second step is to avoid or remove overlap between vertices and vertices with edges. Waddle~\cite{W01} discusses port diagrams (in which vertices are rectangles, and edges attach at a port) to visualize data structures; his goal is to find drawings that avoid crossings within vertices, also see~\cite{KSSH12,SSvH13}. Duncan, Efrat, Kobourov and Wenk~\cite{DEKW06} investigated planar drawings with ``fat edges'', where vertices are disks and edges have thickness.\footnote{The discussion of edges with width and points with extension is much older in ``practical geometry''; Hjlemslev~\cite{H16,H23} attempted an axiomatization, which earned him the scorn of Wittgenstein~\cite[Gesichtsraum, p.59]{W67}.} Van Kreveld~\cite{vK11} recently suggested the notion of bold drawings in which vertices are disks and edges are rectangles.
      In computational biology, such drawings have been suggested for visualizing chromosomes~\cite{FDPK13?}.
      Medieval scholars used a similar style (vertices as disks, edges as ribbons) to visualize squares of opposition (in logic) as we saw in Figure~\ref{fig:VCK8}. Other choices for representing vertices include curves---the string crossing number\index{string crossing number} is based on that idea---and graphs: If we minimize the crossing number by allowing vertices to be replaced by arbitrary connected graphs, we obtain the minor crossing number\index{minor crossing number}.
  \item[Each vertex is represented by a single point.] One can easily imagine a vertex being represented by multiple points. For example, how would the standard crossing number be affected if every vertex could be represented by two points (which together are incident to all the edges incident to the original vertex), we could call this the {\em duplicate crossing number}\index{duplicate crossing number}.\footnote{Bertin~\cite[Figure 19, p.270]{B10} suggests using diagrams in which every vertex is duplicated.} This seems nearly the same (is it?) as asking for the crossing number of the graph on an {\em $n$-spindle}, the pseudosurface resulting from a sphere by pinching (identifying) $n$ pairs of distinct points. If $n = |V(G)|$, then the duplicate crossing number of $G$ is at most the crossing number of $G$ on the $n$-spindle, since we can simply pinch every vertex with its duplicate. The duplicate crossing number also resembles the biplanar crossing number\index{biplanar crossing number}: here too every vertex is represented by two points, but the duplicate points live on a different sphere, so there cannot be an edge between the original and the duplicate vertices. There is research on whether graphs can be planarized by multiplying vertices, following ideas of Fellows and Negami from the 1980s on planar emulators and covers, see~\cite{CDHK11} for a recent overview. Finally, one can turn a cyclic layout into a linear layout by repeating one of the layers (for example, turning a cyclic level crossing number\index{cyclic level crossing number} problem into a $k$-layer crossing number problem\index{k layer crossing number@$k$-layer crossing number}).\footnote{This is beautifully illustrated by an example from Bertin~\cite[Figure 4, p.109]{B10}.}
  \item[Different vertices are mapped to different locations.] This is generally assumed for graph drawings though there are some exceptions. For example, when speaking of realizing a linkage one does not care about vertex overlap, and the definition of a Euclidean graph similarly allows multiple vertices at the same location. For crossing numbers, this has not been a major issue; the only crossing number that allows vertex overlap is the diagonal crossing number\index{diagonal crossing number} introduced by Negami (though one could argue that the simultaneous crossing number\index{simultaneous crossing number} also is an instance). For visualization purposes one could imagine a model in which different vertices are allowed at the same location as long as edges adjacent to a particular vertex are consecutive in the rotation. Buchheim, J{\"u}nger, Menze, Percan~\cite{BJMP06} suggest the notion of bimodal crossing number\index{bimodal crossing number} which has some similarity.
  \item[Edges are not allowed to pass through vertices.] Again this restriction is naturally violated by linkages and Euclidean graphs. For example, a triangle with side-lengths $1$, $1$ and $2$ can only be realized if we allow the edge of length $2$ to pass through the vertex it is not incident on. Edges may also pass through vertices while redrawing the graph, e.g. see~\cite[Theorem 4.6]{PSS09}. We are not aware of any crossing number variant that allows edges to pass through vertices (although it would probably lead to a non-trivial notion if we do not allow edges to make sharp turns while passing through a vertex), unless one interprets the minor crossing number\index{minor crossing number} or Metro-line crossing number in this way\index{Metro-line crossing number}.\footnote{We should mention a recent paper\cite{AAPGCHLRNU13}, that repeatedly uses the term $m+\rcr$ to denote the total number of crossings in a geometric drawing including $m$ crossings of edges through vertices.} Passing through a vertex may be more palatable if vertices are represented not by points but by disks (or disk-homeomorphs), as discussed earlier.
\end{description}

We next turn to issues regarding {\bfseries intersections between edges}.

\begin{description}
  \item[Edges are not allowed to touch.] Without becoming too technical, let us agree that a touching point is a common point of two edges so that at least locally (close to the point), the two edges can be separated  by a line. Allowing touching points leads to undesirable effects. For example, we already mentioned that allowing touching points would trivialize odd crossing number\index{odd crossing number}: take any drawing of a graph, if two edges cross oddly, then add a touching point between them close to one of the crossings, so all pairs of edges cross evenly (since a touching point would count as a crossing), showing that every graph has odd crossing number $0$ if touching points are allowed. Another variant that would be affected is the maximum crossing number; if we allow touching points, $C_4$ can be drawn with $2$ ``crossings'', but it is known that $C_4$ is not thrackleable, so its maximum crossing number (under the standard definition) is $1$.

      The real reason touching points are undesirable, however, is that they lead to ambiguous drawings. While a drawing is defined as a mapping, we only see the result of the mapping, which is a subset of the plane (or some surface). Even if we assume that we know where the vertices are located we may not be able to distinguish a crossing point from a touching point just by looking at the drawing: imagine four curves entering a point, two from the left and two from the right, all with one common tangent. Then the drawing does not tell us whether we are looking at a crossing or touching point. The problem remains even if the curves don't meet at a common tangent:
      when we see an intersection looking like an $x$ we automatically assume that it's a crossing, however, if touching points are allowed that need not be the case since we generally do not assume that the curves used to represent edges are smooth (polygonal arcs are common in representing edges, so a restriction to smooth curves would exclude a popular way of drawing edges).

  \item[No self-intersections.] Do we allow edges to intersect themselves (either crossing or touching)? This issue is rarely discussed (if one thinks of an edge as adjacent to itself then a prohibition on adjacent crossings will automatically exclude self-intersections). The presence or absence of self-intersection is the difference between Pach and T\'{o}th's degenerate crossing number\index{degenerate crossing number}, $\dcr(G)$, and Mohar's genus crossing number~\cite{M09}\index{genus crossing number}, $\gcr(G)$. Mohar conjectures that $\dcr(G) = \gcr(G)$, but this seems far from obvious. Similarly, it is not clear whether allowing self-intersections reduces $\acr_+$, one of the algebraic crossing numbers. Since edges are equipped with directions for algebraic crossing numbers\index{algebraic crossing number}, the standard trick for removing self-intersections does not work, see~\cite{FPSS12b}.

  \item[The number of intersections in the drawing is finite.] We do not allow two edges to overlap in more than a finite number of points. If some drawing style (like confluent drawings) seems to require this, we introduce an intermediate representation (train tracks consisting of branches and switches in confluent drawings), and define the crossing numbers for that representation instead of for the underlying graph.
\end{description}

So even at this basic level there is reasonable room for disagreement on what makes a drawing. Different crossing numbers have different demands, and a single definition will not do all of them justice, but let us try. We will generally understand a {\em drawing} to fulfill the following requirements: each vertex will be represented by a unique point. An edge $e$ in a drawing is a homeomorphic mapping from $[0,1]$ to the topological space of the drawing so that $e(0)$ and $e(1)$ are the endpoints of the edge, and $e(0,1)$ does not contain any vertices. An {\em intersection} of two edges $e$ and $f$ is a point $(s,t) \in [0,1]^2$ so that $e(s) = f(t)$; two edges are not allowed to touch. If $(s,t) \in (0,1)^2$ we call the intersection a {\em crossing}. By definition, any intersection that is not a crossing must be a common endpoint. We require that the total number of intersections in a graph is finite.

This notion of drawing will work for most crossing numbers we will see below. There are two conditions we will occasionally relax: we will allow edges to touch for some variants, and an edge will sometimes just be a continuous mapping from $[0,1]$ to allow self-intersections. A {\em self-intersection} of an edge $e$ is $0\leq s<t \leq 1$ so that $e(s) = e(t)$, it is a {\em self-crossing} if $0 < s< t<1$. The only self-intersection which is not a self-crossing is an endpoint of a loop (in multigraphs).
At the next level we consider additional assumptions that are sometimes made on drawings. Drawings with these additional properties are typically called normal or good. It is often the case that crossing number optimal drawings, that is, drawings which minimize the value of a crossing number for a given graph have all of these properties, so sometimes they are assumed automatically. This assumption is fair for the standard crossing number\footnote{As was realized early on, e.g.\ in~\cite{R64,K68}.}, but it does fail for some other variants (e.g.\ in a constrained crossing number optimal drawing two edges may have to cross more than once~\cite{MZ99}). So we will not generally require these additional properties. They have been discussed in detail by Sz{\'e}kely~\cite{S04}, but also by Winterbach~\cite{W05}.

\begin{description}
  \item[Every two edges cross at most once.] Drawings in which every two edges cross at most once are often called {\em simple}, but this term has at least three identifiable meanings. The original definition may go back to Ringel~\cite{R64} who used simple to mean that every two edges intersect at most once (so adjacent edges cannot cross). This is more restrictive than only requiring that every two edges cross at most once. If we want to make this distinction, we will use {\em intersection-simple}\mindex{intersection-simple} (for Ringel's notion) versus {\em crossing-simple}\mindex{crossing-simple} or just {\em simple}\mindex{simple} (since this usage is more common these days). The third meaning of simple is to only allow each edge to cross at most one other edge. We will avoid using simple with this third meaning (unfortunately, the simple crossing number\index{simple crossing number} is named for this stricter notion of simplicity). We follow tradition in denoting crossing number variants that assume their drawings are simple by placing a $*$ in the super-index; requiring drawings to be simple does not affect most crossing numbers, e.g.\ $\cro^* = \cro = \pcr^* = \ocr^* = \acr^*$.\footnote{$\cro^*$ should not be confused with the simple crossing number which is based on a stronger requirement: each edge is allowed to cross at most one other edge.} There are some exceptions, however. A drawing realizing the constrained crossing number\index{constrained crossing number}, the degenerate crossing number\index{degenerate crossing number} or the local crossing number \index{local crossing number} of a graph may require edges crossing multiple times.
  \item[Adjacent edges do not cross each other.] This rule was called Rule $+$ by Pach and T\'{o}th~\cite{PT00b}; the similar-looking Rule $-$ is not a drawing rule but affects the counting of crossings: crossings of adjacent edges are allowed, but they do not count. For the standard crossing number, $\cro = \cro_+$\index{crossing number}, but no similar results are known for other crossing numbers. The only separations we are aware of are for the monotone odd crossing number\index{monotone odd crossing number}, $\mocr$, here $\mocr(G) < \mocr_+(G)$ for some graph $G$~\cite{FPSS12b}, and the local crossing number\index{local crossing number}, where $\lcr(G) < \lcr^*(G)$ is possible. The odd crossing number\index{odd crossing number} is sensitive to the effects of Rule $-$: $\iocr(G) < \ocr(G)$ for some graph $G$~\cite{FPSS12b}.

\end{description}

Finally, there is one more requirement which is often made:

\begin{description}
  \item[At most two edges cross in any point.] Depending on how we count, this requirement is not strictly speaking necessary: a crossing is a common interior point of two edges. If $k$ edges cross in the same point, then there are ${k \choose 2}$ crossings by definition of crossing. To make this point clear, many definitions use {\em pairwise crossing} in the definition of crossing number.\footnote{While this clarified the method of counting, assuming the reader understood that that was the intention, it may have been a small step in the confusion of the crossing number with the pair crossing number.} A crossing shared by $k$ (distinct) edges can be replaced by $k$ (double-) crossings by perturbing the edges.\footnote{Tait~\cite{T1877} in 1877 describes this as follows: ``By infinitesimal changes of position of the branches intersecting in it, a triple point is decomposable into $3$ double points, a quadruple point into $6$, and generally an $x$-ple point into $\frac{x(x-1)}{1\cdot2}$ double points''. Tait is taking about closed plane curves. } This assumes that we do not allow touching points, that is, every two edges actually cross at the crossing point (otherwise perturbations may introduce more than $k$ crossings which may, or may not, be reducible based on other drawing conventions).
\end{description}


\subsubsection{Style of Drawing}\label{sec:SoD}

Once we get beyond the basics of what constitutes a drawing there are various choices to be made that influence
the appearance of the drawing, vertices and edges, as a whole; we are calling this the {\em style of the drawing},
an admittedly vague term. There seems to have been very little systematic work on this with the exception of Bertin's ``Semiology of Graphics'' (originally published in 1967). Bertin's book contains a valuable section on networks~\cite[Part II]{B10} which could form the basis of a modern treatment from the perspective of graph drawing. Bertin identifies, among others, linear drawings (book drawings in two pages), circular (that is, convex) drawings, hierarchical drawings, and perspective drawings. For example, about convex drawings he writes ``By arranging the elements [\ldots] on a a circle, any relationship can be transcribed by a straight line. This is the construction which produces the least confusing images, whatever the number of intersections stemming from the raw data.''~\cite[p. 271]{B10}. This seems like good common sense, and sociologists had used this technique for years~\cite{M34,B45,M53}, but there has been little experimental work on this. Purchase~\cite{P02,P04a} has started investigating metrics based on common aesthetic criteria (including crossing minimization, bend minimization, and angle resolution), and there has also been recent work on angle resolution in particular~\cite{HHE08,H08a}, and how different drawing aesthetics combine~\cite{HEHL12, HHL12}.

If we look at what drawings researchers have used in practice, two dominant styles emerge, both focussed on edges. Edges are either drawn as curves (or polygonal arcs for computational purposes) or as straight-line segments (or geodesics in metric surfaces).\footnote{Eppstein~\cite{E13a} has given us a detailed summary and history of various curve drawing styles. Many of those have not been explored in the context of crossing minimization.} Not surprisingly, the traditional crossing number, $\cro$\index{crossing number}, and the rectilinear crossing number\index{rectilinear crossing number}, $\rcr$, have remained the main crossing number variants, and many other crossing numbers are wedged between $\cro$ and $\rcr$ since they are obtained by restricting $\cro$ or relaxing $\rcr$. Some variants have been based on restricting common parameters for these drawings; e.g.\ the $t$-polygonal crossing number\index{t polygonal crossing number@$t$-polygonal crossing number} allows at most $t-1$ {\em bends} in each edge. One could imagine restricting the number of available {\em slopes} ($t$-polygonal, $k$-slope crossing number)\index{t polygonal k slope crossing number@$t$-polygonal $k$-slope crossing number} or the set of available slopes (e.g.\ orthogonal drawings, in which all edge segments are axis-parallel), but, as far as we know, this has only been studied for embeddings, not drawings; the crossing minimization problem for port diagrams, which often employ orthogonal drawings, has been studied~\cite{W01,KSSH12,SSvH13}, but no crossing number notion has been explicitly defined. Finally, one can control the angles at which edges meet; the {\em angular resolution} of a drawing is the smallest angle between any two edges at a common endpoint; more recently, the {\em crossing resolution} of a drawing has been introduced as the smallest angle between any two edges at a crossing~\cite{DGDLM11}; in {\em RAC (right-angle crossing) drawings} all crossings have to be at right-angles~\cite{DEL11}. Recent progress on the rectilinear crossing number\index{rectilinear crossing number} has been based on relaxing the rectilinear drawing requirement to pseudolinear drawings, leading to the
pseudolinear crossing number, $\pscr$\index{pseudolinear crossing number}. It seems to capture both the combinatorial and geometric nature of the rectilinear crossing number well enough to have led to the conjecture that $\pscr(K_n) = \rcr(K_n)$~\cite{BLPRS07}, but so far this crossing number has not been investigated for other graphs (with the exception of~\cite{HVLS14}). Further relaxing pseudolinearity to $x$-monotonicity leads to a whole group of crossing numbers (monotone crossing numbers)\index{monotone crossing number}.

A couple of other drawing styles have been added to the graph drawing toolbox recently; there are Lombardi drawings~\cite{DEGKN11}, partially drawn lines~\cite{BEW95,BK12}, drawings with fat edges~\cite{DEKW06}, and bold drawings~\cite{vK11}, though we are not aware of any crossing number variants based on them. However, reviewing the compendium of crossing number variants suggests that style decisions are typically not made for purely aesthetic reasons, but to reflect some structural characteristics of the graph. For example, the vertices of the graph may be ordered, in $x$ or $y$-direction (or both) and a drawing has to represent this ordering (or both orderings), or the graph may be bipartite or $k$-partite, suggesting drawings in which vertices in the same partition are grouped together. There is not always a need to create a new name or symbol for a crossing number that is created in this way; for example, if we weight the edges of the graph, it is quite natural to interpret $\cro(e,f)$ as $w(e) \cdot w(f)$ and we can continue to write $\cro(G)$ for the weighted crossing number\index{weighted crossing number} of $G$, or $\cro(G,w)$ is we want to emphasize that $G$ is equipped with a special structure. The following list collects style choices made based on structural features of the graph.

\begin{description}
  \item[Orderings of the vertices.] If the vertices of the graph are equipped with a total or partial order, it seems natural to arrange the vertices along a line (or a circle), but then additional restrictions on drawing the edges are necessary to get new variants. For the line, this is done by the fixed linear (total order)\index{fixed linear crossing number} and the anchored (partial order) crossing numbers\index{anchored crossing number}. If one interprets the ordering as ordering the $x$-coordinates of the vertices and one requires edges to be drawn as straight-line segments (or $x$-monotone curves), one gets variants of the monotone\index{monotone crossing number} or leveled crossing numbers\index{leveled crossing number}. If one interprets the ordering as ordering the vertices by distance from the origin, one gets the radial crossing number\index{radial crossing number}. If one interprets the ordering as an angular ordering around the origin, one gets the cyclic level crossing number\index{cyclic level crossing number}.

      One could also imagine vertices being ordered with respect to both $x$- and $y$-coordinates (corresponding to directions NW, NE, SE, SW). Eades, Lai, Misue, and Sugiyama~\cite{ELMS91,MELS95} called this an {\em orthogonal ordering} and studied it as a way to preserve the mental map of a graph in a redrawing. In crossing number terms, this suggests the (so far) uninvestigated bi-monotone crossing number\index{bi-monotone crossing number}.

  \item[Partite Graphs.] For bipartite or $k$-partite graphs it is natural to require that all vertices in a particular partition are somehow grouped together; for example, they may lie on a common straight line. For $k=2$ this gives the bipartite crossing number\index{bipartite crossing number}. For larger $k$ there is the convex $k$-partite crossing number\index{convex k partite crossing number@convex $k$-partite crossing number} which requires the vertices to lie on the boundary of a disk so that vertices in the same partition are consecutive. Partitions can also be placed on concentric circles (radial crossing number\index{radial crossing number}), or parallel lines. If the partitions are ordered (and the vertices are assigned to fixed partitions), we are back in the ``Orderings of vertices case'' with radial and leveled crossing number. So far, there hasn't been an attempt at a free radial or a free leveled crossing number.

  \item[Ordering of edges at vertices.] If we prescribe, at each vertex, the cyclic ordering of the ends of edges at that vertex, the {\em rotation}\index{rotational crossing number}, we are looking at crossing numbers with rotation system. There may also be restrictions on the rotation system based
      on other structural properties. For example, in a directed graph we may want all the incoming and all the outgoing edges to be consecutive, giving us the bimodal crossing number\index{bimodal crossing number}. Another way in which the rotation at a vertex can be constrained is by identifying its neighbors with leaves of a tree and restricting the ordering of the leaves to an ordering corresponding to an embedding of the tree. This is related to the idea of tanglegrams\index{tanglegram} in computational biology, and has been studied for the bipartite crossing number\index{bipartite crossing number}, and the {$k$-layer crossing number}\index{k layer crossing number@$k$-layer crossing number}.

  \item[Directed edges.] A directed acyclic graph can be understood as a graph with a partial ordering of the vertices, leading to hierarchical drawings (upward crossing number\index{upward crossing number}), recurrent hierarchical drawings (the uninvestigated clockwise crossing number\index{crosswise crossing number}) or, less restrictive, bimodal drawings (bimodal crossing number\index{bimodal crossing number}).

  \item[Disconnected graph.] There is not much to say about disconnected graphs in the plane, components are typically moved apart and drawn separately. Interesting problems start appearing when a disconnected graph is drawn on a higher-genus surface.

  \item[Pairs of Graphs.] Pairs (or tuples) of graphs are no different from disconnected graphs, unless there is some type of interaction between the graphs, for example, a shared vertex set. At that point, there are drawing styles to model different types of interaction,
      e.g.\ simultaneous crossing number\index{simultaneous crossing number} (shared vertices and edges), red/blue crossing number\index{red/blue crossing number} and joint crossing numbers\index{joint crossing numbers} (shared canvas).

  \item[Edge-coloring.] If a graph has multiple edges, we can think of the graph as a union of multiple graphs on the same vertex set and apply ideas from ``Pairs of Graphs''. We could also assign different weights to crossings depending on the colors of the edges that cross (weighted crossing number\index{weighted crossing number}); one particular example would be to only count crossings between edges of the same color (simultaneous crossing number\index{simultaneous crossing number}) or different color (red/blue crossing number\index{red/blue crossing number}). On the other hand, some visualizations, such as metro-line drawings, are naturally done using edge colorings.

  \item[Edge-weights.] Simple edge weights can be modeled using the weighted crossing number\index{weighted crossing number}.

  \item[Labelings.] There are various algorithms and heuristics for labeling graphs, see~\cite{KT?} for a survey. Labels can be drawn within the object to which they apply, leading to styles in which edges and vertices are thickened up as in ~\cite{DEKW06,vK11} or the medieval drawings mentioned in Remark~\ref{rem:DC}. We are not aware of any crossing number variants taking the presence of labels into account.

  \item[Vertex-coloring.] If the vertex coloring is proper, we are back in the case of partite graphs. If it is not, different colors may denote different types of vertices. E.g.\ the color of a vertex may encode which boundary component (of a surface with holes) a vertex lies on.

  \item[Partially embedded graphs.] One may want to minimize the number of crossings in the drawing of a graph $G$ which has been partially embedded, this leads to the constrained crossing number\index{constrained crossing number}. Interesting, but as far as we know, uninvestigated, special cases occur if the locations of some (or all) of the vertices are fixed and the number of bends along each edge is restricted.

  \item[Clusters.] There has been much research on clustered drawings in which vertices are grouped into hierarchically nested regions. There are various types of crossings (edge-edge, edge-region, region-region). Typically, all of these crossings are prohibited, and there is significant research on $c$-planarity (clustered planarity) whose complexity it still open. Recently a first step was taken into allowing some of these types of crossings~\cite{ADLDBFR12}, but a formal notion of a {\em clustered crossing number}\mindex{clustered crossing number} has not yet been introduced. In the visualization of large data sets, one can imagine vertices being located in given geometric clusters, for example the tiles of a $2$-dimensional grid, and counting the crossings between edges and tile boundaries~\cite{CMG13}.
\end{description}

%We could also think of knot crossing numbers this way: the graphs are given with a drawing and a decision,
%at each crossing, which edge passes over the other (encoded by a $\pm 1$ for each crossing).

\subsubsection{Drawing Surface}\label{sec:DS}

It's natural to think of a crossing as happening in the plane, so it's hardly surprising that crossing numbers are typically defined for the plane or for locally planar manifolds: surfaces, in other words.

We need to decide on which surface we draw the graph; typically, this is the plane or the two-dimensional sphere $S^2$ (which can make a difference if metric conditions are in place, as in the geodesic crossing number\index{geodesic crossing number}). Crossing numbers on other surfaces, orientable, $S_g$, and non-orientable, $N_g$, were investigated in the earliest papers, including the toroidal crossing number~\cite{GJ69}\index{toroidal crossing number} and crossing numbers on the Klein bottle~\cite{K69}\index{Klein bottle crossing number}. Often special notations were introduced for surface drawings; we'll follow the convention to write the surface in the index; so $\cro_{N_1}$ is the projective plane crossing number\index{projective plane crossing number} and $\pcr_{S_1}$ is the toroidal pair crossing number\index{toroidal pair crossing number} (which has not been investigated as far as we know).

The surface may have holes, in which case some vertices may be forced to lie in certain boundary components (for two holes: radial crossing number with two levels\index{radial crossing number}), maybe with their order specified (map crossing number\index{map crossing number}, anchored crossing number\index{anchored crossing number}). We may also allow disconnected surfaces, for example multiple planes (the $k$-planar crossing number\index{k planar crossing number@$k$-planar crossing number}).

If we drop the restriction that a manifold be locally planar, we can explore pinched surfaces (such as the spindle) or branched surfaces. Neither of these choices is well-investigated, with the exception of books. Book crossing numbers\index{book crossing number} are typically defined by disallowing edges to cross the spine, so crossings cannot occur on the spine (where the manifold is not locally planar). On the other hand, one may decide to allow edges crossing the spine and try to minimize the number of spine crossings (spine crossing number\index{spine crossing number}). For pinched surfaces it is not immediately clear what constitutes a proper drawing (are vertices allowed to lie in pinches, how many edges can pass through a pinched point, may an edge pass through a pinched point without crossing to the other part of the surface, how do we count the crossings, what if we have triple pinches, etc.).

Finally, we can consider drawing the graph in other manifolds, $3$-dimensional space, for example. There is the grid crossing number\index{grid crossing number}, in which graphs are drawn on $d$-dimensional grids of limited size, and the space crossing number\index{space crossing number}, which has the flavor of a stabbing number.\footnote{There also is a notion of crossing number for geometric hypergraphs, in which hyperedges are represented as simplices, see~\cite{AS13}.}

\subsection{Methods of Counting}

In German a crossing of curves is called a ``Doppelpunkt''~\cite{S23,D36}, a double point. This term stems from the algebraic tradition and survives in knot theory, but even in graph drawing pairwise counting of crossings is the preferred method, that is, $k$ edges passing through the same point count for ${k \choose 2}$ crossings. One can imagine counting a $k$-wise crossing just once (degenerate crossing number\index{degenerate crossing number}, genus crossing number\index{genus crossing number}) or $k$ times\footnote{The later variant seems not to have been studied; some subtleties immediately arise (as they do for the degenerate crossing number): do we allow an edge to pass through the same point multiple times? Do edges have to cross when passing through the point or may they touch? Do we count every crossing, or do we just count the number of edges involved?}. As we saw in the short historical section, the algebraic way of counting crossings may precede this way of counting crossings; edges are oriented, and for an ordered pair $(e,f)$ of edges we can assign a crossing a $+1$ or $-1$ depending on whether $f$ crosses $e$ from left to right or from right to left. For weighted graphs, it is natural to assign weights to crossings, typically using the product of the weights of the edges involved (as far as we know, real weights or weights from other algebraic structures have not been studied). Continuing the philosophy of pairwise counting, the weighted crossing number\index{weighted crossing number} allows one to assign weights to pairs of edges.

When computing the number of crossings between two edges, $\psi(e,f)$, most crossing numbers $\psi$ add up the counts of the pairwise crossings of $e$ and $f$. There are some exceptions: the pair crossing number takes the maximum (so each pair contributes at most once, namely if it crosses), the odd crossing number\index{odd crossing number} adds up crossings modulo $2$, and the algebraic crossing number\index{algebraic crossing number} takes the absolute value of the sum.

To calculate the crossing number of a drawing, most crossing numbers simply add up the pairwise crossings. As we saw earlier, the local crossing number\index{local crossing number} takes the maximum per edge:  $\max_{e \in E} \sum_{f \in E} \cro(e,f)$. Independent crossing number variants do not include pairs of adjacent edges in the count (independent crossing number\index{independent crossing number}, independent odd crossing number, etc.).

Finally, to determine the crossing number of a graph we typically minimize the crossing number over all drawings, although there is the family of maximum crossing numbers (maximum crossing number\index{maximum crossing number}, maximum rectilinear crossing number\index{maximum rectilinear crossing number}, maximum orchard crossing number\index{maximum orchard crossing number}).

Some crossing numbers count crossings other than edge crossings, e.g.\ the spine\index{spine crossing number}, orchard\index{orchard crossing number}, edge\index{edge crossing number} and space crossing numbers\index{space crossing number}.

\subsection{Modes of Representation}

This leaves us with modes of representation of graphs; there is not much to be said here; the standard mode of representation where a curve between two points is taken to represent the edge connecting the vertices corresponding to the points is predominant. The only alternative model we have seen in the context of crossing numbers is that of confluent drawings introduced by Dickerson, Eppstein, Goodrich, and Meng~\cite{DEGM05}. A graph is drawn like a train track (with branches and switches), vertices correspond to stations, and an edge to a legal train route (trains cannot make sharp turns at switches).\footnote{Roger Penrose uses a similar idea in his, or his father's, railway mazes~\cite{DDR08}.} If we allow bridges, points at which one track crosses over another track, then
the confluent crossing number\index{confluent crossing number} is the smallest number of bridges necessary to realize the train track.

\begin{question}
    Using the confluent drawing style (rather than its semantics) as an inspiration, we could allow edges in a drawing to run in parallel temporarily and then separate again (without changing order), just like in a confluent drawing but without the connotation for connectivity. Now let us say we count the crossing of two such bundles of edges as a single crossing (as opposed to weighing it by the number of edges in the bundle), do we get an interesting notion of crossing number? Should we require that every bundle contains each edge at most once? In an actual drawing we may decide to keep the edges in a bundle slightly separate, maybe by using color for the intervening spaces. This idea has recently been studied in the context of the Metro-line crossing number\index{Metro-line crossing number} under the name ``block crossing''~\cite{FP13}.\mindex{block crossing}
\end{question}

There is one other model of representation that has not been explored yet in the context of crossing numbers: representing graphs as intersection graphs. String graphs will serve as an example. We know that every planar graph is the intersection graph of strings (curves), indeed at this point we know that we can assume that each pair of strings crosses at most once~\cite{CGO11}, and that the strings are straight-line segments~\cite{CG09} (we do not yet know whether they can be chosen in at most $4$ directions, this would imply the $4$-color theorem). So in the string representation every vertex becomes a curve (or straight-line segment) and an edge corresponds to a (single) crossing of the curves. One could imagine extending this model by distinguishing two types of crossings: crossings representing edges and crossings that count towards a {\em string crossing number}\index{string crossing number}. In a drawing the later crossings could be represented by overpasses (as for knots). We are not aware that this approach has been investigated. (The existing string crossing number realizes a slightly different idea.)

%Visibility representations.

%Simultaneous representations.


\section{A Compendium of Crossing Numbers}\label{sec:C}

For the compendium (and indeed for the rest of the paper), I have always tried to go back to the sources; any result reported at second hand is identified as such. (This does not mean that I guarantee the correctness of all results.) I also made heavy use of other tools such as Vr{\v{t}}o's online bibliography of crossing numbers~\cite{Vx}, MathSciNet, and Google Scholar.

I have tried to be exhaustive, but decided to exclude certain areas altogether rather than covering them badly; this includes crossing numbers for objects other than graphs, most notably knots, braids, hypergraphs\index{hypergraph crossing numbers}~\cite{DP98,C08b}, and permutations~\cite{BBD09}.\footnote{There are also some stabbing number variants called crossing numbers, but the spirit is different; we do not document these variants here.}

For some crossing numbers we had to introduce new notation to avoid conflicts---of which there are many. As the table in Section~\ref{sec:N} shows, nearly every crossing number variant with a parameter $k$ has been called $\nu_k$ or $\cro_k$ at some point; we tried to minimize the proliferation of notation. E.g.\ instead of creating new symbols for the toroidal crossing number or the Klein bottle crossing number, we simply modify the notation for the standard crossing number to include the surface: $\cro_{\Sigma}$ denotes the crossing number on surface $\Sigma$. Similarly, if the underlying graph has structure (rotation, ordering, layering) we don't create a new crossing number notation. For example the fixed linear crossing number is simply the book crossing number, $\bkcr_k$ restricted to drawings which respect the linear ordering of the vertices, so we use $\bkcr_k$ for both variants, writing $\bkcr_k(G,\pi)$ to distinguish the fixed linear crossing number from the book crossing number if necessary. This approach leads to some overloading of notation, but hopefully no confusion.

Many crossing numbers exist under multiple names reflecting various acts of rediscovery; in these cases I've generally decided to go with the older or more established name. In every case, I have tried to document all variant names and symbolism I have encountered.

For each crossing number there is an entry for ``relationships''; this entry is restricted to relationships between crossing number variants and only the most basic parameters: $n = |V|$ and $m = |E|$ (so, in particular, we list all crossing lemmas we are aware of in this rubric). We make no attempt to try capturing relationships with other graph parameters such as the girth, bisection width, cut width, etc.\ or the emerging links between crossing number and chromatic number in the study of Albertson's conjecture~\cite{ACF09}. A recent survey on some of these results is by  Shahrokhi, S{\'y}kora, Sz{\'e}kely, and Vr{\v{t}}o~\cite{SSSV97}.

Finally, we include exact (and some asymptotic) crossing number results for major graph families such as the complete, $K_n$, and complete bipartite graphs, $K_{m,n}$, under the rubric ``values''; for lesser-known crossing number variants we tend to include more detail; we use the usual symbols for graph families, such as $P_n$ for the path on $n$ vertices, $C_n$ for cycles of length $n$, $Q_n = \Box_{i=1}^n K_2$ for the $n$-dimensional hypercube graph, and $W_n$ for the wheel graph (on $n+1$ vertices).

\begin{remark}[Parameters and Derived Notions] For a crossing number $\gamma_k$ parameterized by some parameter $k$, we can define a new parameter $\mu_{\gamma}(G)$ as the smallest $k$ for which $\gamma_k(G) = 0$ if such a $k$ exists. For the (surface) crossing numbers, this gives us (Euler, non-orientable, orientable) genus, for the book (or $k$-page) crossing number, this gives us the notion of pagenumber (or book thickness), for the $k$-planar crossing number, the thickness of a graph, and for the rectilinear $k$-planar crossing number, its geometric thickness; for the (surface) independent odd crossing number we get a homological notion of genus~\cite{SS13}. The grid crossing number has two parameters (dimension and volume) which could be used to define area/volume of a graph. We will mention some of these derived parameters below, but without attempting to survey results concerning them.
\qer \end{remark}

%and where are chromatic, virtual, inner, circle, limit, rainbow, oblivious, Lombardi, Euclidean, game crossing numbers?

\subsection{Notation for Crossing Numbers}\label{sec:N}

The following table lists the crossing numbers with the symbol we use in the current paper (if any) and other notations found in the literature with references; the alternative notations are listed chronologically (at least with respect to the first occurrences we found). The crossing numbers are listed alphabetically by name. There are several crossing number variants for which symbols have never been introduced, including annulus, bimodal, confluent, map, Metro-line, radial, red/blue and spine crossing numbers, these (and some others) are not listed below.

\begin{comment} Crossing numbers without symbols:
annulus &{\em no symbol} & {\em no symbol}\tabularnewline
bimodal & {\em no symbol} & {\em no symbol} \tabularnewline
confluent &{\em no symbol} & {\em no symbol}\tabularnewline
disk &{\em no symbol} & {\em no symbol}\tabularnewline
map &{\em no symbol} & {\em no symbol}\tabularnewline
Metro-line &{\em no symbol} & {\em no symbol}\tabularnewline
pair of pants &{\em no symbol} & {\em no symbol}\tabularnewline
radial &{\em no symbol} & {\em no symbol}\tabularnewline
red/blue &{\em no symbol} & {\em no symbol}\tabularnewline
spine & {\em no symbol} & {\em no symbol}  \tabularnewline
\end{comment}

\medskip
\tablecaption{Crossing number variants with symbols used in the text and in the literature.}\label{tab:cn}
\tablehead{Name (alternate names) & Symbol & Symbol (literature)\tabularnewline\hline}
\begin{supertabular}{>{\raggedright}p{1.8in}|l|>{\raggedright}p{2in}}
abstract topological graph\index{abstract topological graph} & $\cro(G,R)$ & $\mathrm{cr}_{at}$~\cite{K91} \tabularnewline
algebraic\index{algebraic crossing number} & $\acr$ & $\mathrm{acr}$~\cite{PSS08}, $\textsc{acr}$~\cite{T07}, $\textsc{ALG-CR}$~\cite{T08}  \tabularnewline
algebraic $+$  \index{algebraic plus crossing number@algebraic $+$ crossing number}& $\acr_+$ & $\mathrm{acr}_+$~\cite{FPSS12b} \tabularnewline
anchored\index{anchored crossing number} & $\bkcr_k(G,A,\pi)$ & $\mathrm{acr}$~\cite{CM10} \tabularnewline
average\index{average crossing number} & {\em no symbol} & $\mathrm{acr}$~\cite{PR04b} \tabularnewline

bipartite\index{bipartite crossing number} & $\bcr$ &$\nu_2$~\cite{HS71}, $\nu^*$~\cite{M85}, $\mathit{bcr}$~\cite{RT97,SSSV01} \tabularnewline
book ($k$-page)\index{book crossing number} & $\bkcr_k$ & $\nu_k$~\cite{SSSV95,W05} \tabularnewline
book edge ($k$-page edge)\index{book edge crossing number} & {\em no symbol} & $\mathrm{cre}_k$~\cite{BES13} \tabularnewline

convex (outerplanar, circular)\index{convex crossing number} & $\bkcr_1$ & $\mathrm{cr}^*$, $\nu_1$~\cite{SSSV95},
$\chi$~\cite{BB05}, $\mu_+$~\cite{BCGJM?} \tabularnewline
convex maximum rectilinear\index{convex maximum rectilinear crossing number} & $\maxrcr^{\circ}$ & $\mathrm{obf}^{\circ}$~\cite{V08} \tabularnewline
convex $k$-partite (circular $k$-partite)\index{convex $k$-partite crossing number} & {\em no symbol} & $cpr_k$~\cite{R07} \tabularnewline

(minimum, minimal, planar, graph, edge, topological)\index{crossing number} & $\cro$ & $c$~\cite{HH63}, $c_0^+$~\cite{K69}, $\nu$~\cite{G72}, $\nu_*$~\cite{G72b},
    $C$~\cite{FK76}, $\kappa$~\cite{DP98}, $\textsc{cr}$~\cite{PT00b}, $\mathit{cr}_{\mathbb{R}^2}$~\cite{GMS01}, \textit{CR}~\cite{S04}, $\nu_{\RN^2}$~\cite{W05} \tabularnewline
(joint) \index{joint crossing numbers} & $\cro(G_1,G_2)$ & $\mathrm{cr}(G_1,G_2)$~\cite{N01}, $\mathit{cr}(G_1,G_2)$~\cite{AB01}, $C_r(G_1,G_2)$~\cite{WRX11} \tabularnewline
cylindrical\index{cylindrical crossing number} & $\cro_{\circledcirc}$ & {\em no symbol} \tabularnewline
degenerate\index{degenerate crossing number} & $\dcr$ &$\underline{\textsc{CR}}$~\cite{PT09} \tabularnewline
diagonal\index{diagonal crossing number} & $\diagcr$ & $\mathrm{cr}_{\Delta}$~\cite{N01} \tabularnewline

edge\index{edge crossing number} & $\ecr$ & {\em no symbol} \tabularnewline

fixed linear\index{fixed linear crossing number} & $\bkcr_k(G,\pi)$ & $\nu_{\pi}$~\cite{MNKF90} (for $k=2$), $\nu_L$~\cite{C06} (for $k=2$),
$\nu_{L,k}$~\cite{CM07}, $\mu$~\cite{Z12} (for $k=1$) \tabularnewline
genus\index{genus crossing number} & $\gcr$ &$\mathrm{GCR}$~\cite{M09} \tabularnewline
genus $g$ (surface)\index{genus g crossing number@genus $g$ crossing number}\index{surface crossing number} & $\cro_{S_g}$ & $c^+_g$~\cite{K69}, $cr_g$~\cite{K72}, $cr^*_g$~\cite{K78} \tabularnewline
genus $g$ local (local $g$)\index{genus g local crossing number@genus $g$ local crossing number} & $\lcr_{S_g}$ & $\lambda_g$~\cite{K73} \tabularnewline
($d$-dimensional volume $N$) grid\index{grid crossing number} & $\gridcr(G,N,d)$ & $\cro$~\cite{DMS14} \tabularnewline

independent\index{independent crossing number}    & $\cro_-$ & $\textsc{cr}_-$~\cite{PT00b} \tabularnewline
independent algebraic\index{independent algebraic crossing number} & $\iacr$ & $s$~\cite{T70},  $\textsc{iacr}$~\cite{T07},
        $\textsc{IALG-CR}$~\cite{T08}, $\mathrm{acr}_-$~\cite{FPSS12b}  \tabularnewline
independent odd\index{independent odd crossing number} & $\iocr$ & $\textsc{odd-cr}_-$~\cite{PT00b}, $\textit{CR-IODD}$~\cite{S04}, $\nu^{(i)}$~\cite{W05},
$\mathrm{iocr}$~\cite{PSS07d},  $\operatorname{\mathit{cr-iodd}}$~\cite{M09b}  \tabularnewline
independent pair\index{independent pair crossing number} & $\pcr_-$ & $\textsc{pair-cr}_-$~\cite{PT00b}, $\mathrm{pcr}_-$~\cite{FPSS12b} \tabularnewline

$k$-layer \index{k layer crossing number@$k$-layer crossing number} & {\em no symbol} & $K$~\cite{W77} \tabularnewline
Klein bottle\index{Klein bottle crossing number} & $\cro_{N_2}$ & $\mathrm{cr}_2$~\cite{K69}, $\overline{\overline{\mathit{cr}_2}}$~\cite{R01}, $\mathit{cr}_{\mathbb{K}}$~\cite{GMS01} \tabularnewline

leveled\index{leveled crossing number} & $\mcro_{\preceq}(G)$ & $\mathrm{mon-cr}(G,\ell)$~\cite{FPSS12b} \tabularnewline
linear ($2$-page)\index{linear crossing number}\index{free linear crossing number} & $\bkcr_2$ & $\mu$~\cite{BCGJM?} \tabularnewline
local (crossing parameter)\index{local crossing number} & $\lcr$  & $\lambda_0$~\cite{K73}, $\mathit{lcn}$~\cite{C92}, $\crs$~\cite{BG07},
$c$~\cite{SG10}, $\xi$~\cite{GKT13} \tabularnewline
local toroidal\index{local toroidal crossing number} & $\lcr_{S_1}$ & $\ell_1$~\cite{GJS68}, $\lambda_1$~\cite{K73} \tabularnewline

major (major-monotone)\index{major crossing number} & $\Mcr$& $\mathrm{Mcr}$~\cite{BFM06}\tabularnewline

maximum (maximal)\index{maximum crossing number} & $\maxcro$ &$\nu_*$~\cite{G72b}, $\nu_M$~\cite{RSP91}, $\mathrm{cr}^{\mathrm{M}}$~\cite{PRS91}, $\mathrm{CR}$~\cite{HZ95}, $\cro_M$~\cite{A09} \tabularnewline
maximum orchard\index{maximum orchard crossing number} & {\em no symbol} & $\mathrm{MOCN}$~\cite{FG09} \tabularnewline
maximum rectilinear \hfill (maximal rectilinear, obfuscation complexity) & $\maxrcr$
    &$\overline{\nu}_*$~\cite{G72b}, $M$~\cite{FK76},
    $\overline{\nu}^+$~\cite{H83}, $\nu'_M$~\cite{RSP91}, $\overline{\mathrm{CR}}$~\cite{AFH09}, $\obf$~\cite{V08} \tabularnewline
maximum rectilinear edge \index{maximum rectilinear edge crossing number}& $\maxrecr$ & {\em no symbol} \tabularnewline

minor (minor-monotone)\index{minor crossing number} & $\mcr$& $\mathrm{mcr}$~\cite{BFM06}\tabularnewline

monotone\index{monotone crossing number}  & $\mcro$ & \textrm{mon-cr}~\cite{FPSS12b}, $\textsc{mon-cr}$~\cite{PT112} \tabularnewline
monotone independent odd\index{monotone independent odd crossing number} & $\miocr$ & \textrm{mon-iocr}~\cite{FPSS12b}, \textrm{mon-ocr}$_{-}$~\cite{BFK13}\tabularnewline
monotone odd\index{monotone odd crossing number} & $\mocr$ & \textrm{mon-ocr}~\cite{FPSS12b} \tabularnewline
monotone odd $+$\index{monotone odd plus crossing number@monotone odd $+$ crossing number} (monotone semisimple odd)& $\mocr_{+}$ & \textrm{mon-ocr}$_{+}$~\cite{BFK13} \tabularnewline
monotone odd $\pm$\index{monotone odd plus minus crossing number@monotone odd $\pm$ crossing number} (monotone weakly semisimple odd)& \textrm{mon-ocr}$_{\pm}$ & $\mocr_{\pm}$~\cite{BFK13} \tabularnewline
monotone pair\index{monotone pair crossing number} & $\mpcr$ & $\operatorname{pair-cr^{mon}}$~\cite{V04}\tabularnewline

nodal\index{nodal crossing number} & $\ncr$ &  {\em no symbol} \tabularnewline
nodal toroidal\index{nodal toroidal crossing number} & $\ncr_{S_1}$ & $n_1$~\cite{GJS68} \tabularnewline

non-orientable genus $g$\index{non-orientable genus $g$ crossing number} & $\cro_{N_g}$ & $c_g$~\cite{K69}, $\widetilde{cr}_g$~\cite{K72b}, $cr_g$~\cite{K78} \tabularnewline

odd\index{odd crossing number} & $\ocr$ & $\textsc{odd-cr}$~\cite{PT00} , $\mathrm{cr_{odd}}$~\cite{H03}, \textit{CR-ODD}~\cite{S04},  $\nu^{(o)}$~\cite{W05}, $\mathrm{ocr}$~\cite{PSS07d}, $\operatorname{\mathit{cr-odd}}$~\cite{M09b}  \tabularnewline
odd $+$\index{odd plus crossing number@odd $+$ crossing number}   & $\ocr_+$ & $\textsc{odd-cr}_+$~\cite{PT00b} \tabularnewline
orchard\index{orchard crossing number} & $\orccr$ & $\mathrm{OCN}$~\cite{FG09} \tabularnewline
oriented (joint)\index{oriented crossing number} & $\orcr$ & $\mathrm{cr}_+$~\cite{N01} \tabularnewline

pair (pairwise)\index{pair crossing number} & $\pcr$ & $\textsc{pair-cr}$~\cite{PT00}, $\mathrm{cr_{pair}}$~\cite{H03},  $\mathrm{pcr}$~\cite{KM04}, $\operatorname{pair-cr}$~\cite{V04}, \textit{CR-PAIR}~\cite{S04}, $\nu^{(p)}$~\cite{W05},  $\operatorname{\mathit{cr-pair}}$~\cite{M09b}\tabularnewline
pair $+$\index{pair plus crossing number@pair $+$ crossing number}   & $\pcr_+$ & $\textsc{pair-cr}_+$~\cite{PT00b}, $\mathrm{pcr}_+$~\cite{FPSS12b} \tabularnewline
$k$-planar\index{k planar crossing number@$k$-planar crossing number} & $\cro_k$ & $\mathrm{Cr}_k$~\cite{O71}, \textit{CR}$_k$~\cite{S05}, $\nu_k^{(B)}$~\cite{W05}, $\mathrm{cr}_k$~\cite{SSSV07} \tabularnewline
$t$-polygonal\index{t polygonal crossing number@$t$-polygonal crossing number} & $\rcr_t$ &$\cro_t$~\cite{B91} \tabularnewline

projective plane\index{projective plane crossing number} & $\cro_{N_1}$ & $\mathrm{cr}_1$~\cite{K69}, $\mathit{cr}_{\mathbb{P}}$~\cite{GMS01}, $\mathrm{cr}_p$~\cite{MR08}\tabularnewline
pseudolinear\index{pseudolinear crossing number} & $\pscr$ & $\widetilde{\mathrm cr}$~\cite{BLPRS07} \tabularnewline

rectilinear (straight-line, linear, geometric)\index{rectilinear crossing number} & $\rcr$ & $\overline{c}$~\cite{HH63}, $\overline{cr}$~\cite{J71},
    $\overline{\nu}$~\cite{G72}, $\overline{\nu}_*$~\cite{G72b},
    $\overline{\mathrm{cr}}$, $R$~\cite{FK76}, $\nu'$~\cite{RSP91}, $\mathrm{cr}_1$~\cite{BD92}, $\overline{\kappa}$~\cite{W97},
    \textsc{lin-cr}~\cite{ST02}, \textit{CR-LIN}~\cite{S04}, $\mathrm{rcr}$~\cite{PSS05a}, $\overline{\mathrm{cr}}_1$~\cite{BCGJM?},  $\operatorname{\mathit{cr-lin}}$~\cite{M09b}  \tabularnewline

rectilinear edge\index{rectilinear edge crossing number} & $\recr$ & {\em no symbol} \tabularnewline
rectilinear $k$-planar\index{rectilinear k planar crossing number@rectilinear $k$-planar crossing number} & $\rcr_k$ & $\overline{\mathrm{cr}}_k$~\cite{SSSV07} \tabularnewline
rectilinear space\index{rectilinear space crossing number} & $\rspcr$ & $\operatorname{lin-cr}_4$~\cite{BH11} \tabularnewline
simple\index{simple crossing number}  & $\cro^{\times}$ & $\mathrm{scr}$~\cite{C08b}, $\mathrm{crs}$~\cite{BEJKMW06} \tabularnewline
simple degenerate\index{simple degenerate crossing number} & $\dcr^*$ &$\textsc{CR}^*$~\cite{PT09}, $cr^*$~\cite{AP13} \tabularnewline
simple local\index{simple local crossing number} & $\lcr^*$ & {\em no symbol} \tabularnewline
simultaneous\index{simultaneous crossing number} & $\scr$ & $\mathrm{scr}$~\cite{CJS08}, $\mathrm{simcr}$~\cite{C08b}\tabularnewline
simultaneous geometric\index{simultaneous geometric crossing number} & $\sgcr$ & {\em no symbol}\tabularnewline
space\index{space crossing number} & $\spcr$ & $\mathrm{cr}_4$~\cite{BH11} \tabularnewline

spherical\index{spherical crossing number} (spherical geodesic) & $\rcr_{S^2}$ & $\breve{\mathrm{cr}}$~\cite{W06} \tabularnewline
stable\index{stable crossing number}  & {\em no symbol} & $\mathrm{cr}^k$~\cite{K72b}, $\mathrm{cr}_{\gamma(G)-k}$~\cite{KW78} \tabularnewline
string\index{string crossing number} & $\strcr$&  $\mathrm{scr}$~\cite{BCSV10} \tabularnewline
tile\index{tile crossing number} & $\tilecr$ & $\mathrm{tcr}$~\cite{PR04b} \tabularnewline
toroidal\index{toroidal crossing number} (torus)  & $\cro_{S_1}$ & $cr_1$~\cite{GJ69} \tabularnewline
triple\index{triple crossing number} & $\tricr$ & $\mathrm{tcr}$~\cite{TT10} \tabularnewline

upward\index{upward crossing number} & $\mcro_{\preceq}(G)$ & {\em no symbol} \tabularnewline

weighted\index{weighted crossing number}  & {\em no symbol} & $\mathrm{cr}_w$~\cite{SSS08}, $\mathrm{wcr}$~\cite{M08} \tabularnewline
$x$-monotone\index{x-monotone crossing number@$x$-monotone crossing number} & $\mcro_{\preceq}(G)$ & $\operatorname{mon-cr}$~\cite{FPSS12b} \tabularnewline
\end{supertabular}


\subsection{Crossing Numbers}

\begin{comment}
Notation section?

We use the following notation throughout this compendium: $S_g$ is the orientable surface of genus $g$, $N_g$ is the non-orientable surface of non-orientable genus $g$. $S^2$ is the two-dimensional sphere.

$Q_n$ is the $n$-dimensional hypercube

$Z(n)$ is Zarankiewicz's function.
\end{comment}

\begin{comment}
\begin{cn}{ crossing number}
\defn The {\em  crossing number} of $G$,
\reference
\comments
\complexity
\relations
\values
\openq \also
\end{cn}
\end{comment}

\entry{$1$-page crossing number} See convex crossing number, book crossing number.

\entry{$2$-page crossing number} See book crossing number.

\entry{abstract topological graph crossing number} See crossing number of abstract topological graph.

\begin{cn}{Algebraic crossing number}\mindex{algebraic crossing number}\mindex{algebraic plus crossing number@algebraic $+$ crossing number}
\defn Order and orient all edges of $G$ and assign a crossing between edges $e < f$ a $+1$ or $-1$ depending on whether $f$ crosses $e$ from right to left or from left to right at that point. We let $\acr(e,f)$ be the sum of the values of all crossings of $f$ with $e$ (which can be negative). For a given drawing $D$ (and a given orientation) of $G$ we let  $\acr(D) = \sum_{e < f \in E(G)} |\acr(e,f)|$, where $<$ is the ordering of $E(G$).\footnote{The value of $\acr(D)$ does not depend on the orientation, so $\acr(D)$ is well-defined.} The {\em algebraic crossing number} of $G$, $\acr(G)$, is the minimum algebraic crossing number of any drawing of $G$. The Rule $+$ variant of $\acr$ is $\acr_+(G)$, the smallest algebraic crossing number of any drawing of $G$ in which adjacent edges are forbidden to cross. One can define an intermediate variant in which we require $\acr(e,f) = 0$ for every pair of adjacent edges $e$ and $f$; denote this variant by $\acr_{\pm}$
\reference Pelsmajer, Schaefer, {\v S}tefankovi{\v c}~\cite{PSS08}, also Tutte~\cite{T70}, Winterbach~\cite{W05}.
\comments One could argue that this crossing number is implicit in Tutte~\cite{T70}; certainly, the idea of counting crossings algebraically is; however, Tutte insists on not counting adjacent crossings by setting $\acr(e,f) = 0$ for adjacent edges $e$ and $f$; he writes: ``We are taking the view that crossings of adjacent edges are trivial, and easily got rid of.'' If we read this as a claim that $\acr(G) = \iacr(G)$, then we now know that this claim is wrong\index{independent algebraic crossing number}. So Tutte did define $\iacr$, but $\acr$ seems to have first been isolated as a separate notion in~\cite{PSS08}.\footnote{Winterbach~\cite{W05} defines the {\em Tutte crossing number}\mindex{Tutte crossing number}; unlike Tutte, he does not set $\acr(e,f) = 0$ for adjacent edges, but he does order edges by endpoints (to avoid counting both $\acr(e,f)$ and $\acr(f,e)$. As a result he counts some adjacent crossings, e.g. $v_1v_2$ with $v_2v_3$ but not others, e.g. $v_1v_2$ with $v_1v_3$.} There it was asked whether $\acr(G) = \cro(G)$, a question answered by T\'{o}th in the negative~\cite{T08}.
\complexity \NP-complete.\footnote{\NP-hardness is obtained as in Pach and T\'{o}th's proof that $\ocr$ is \NP-hard. The question lies in \NP, since it can be phrased as an integer linear program (this is one way of looking at Tutte's characterization of planarity~\cite{T70}).}
\relations $\iacr(G) \leq \acr(G) \leq \acr_{\pm} \leq \acr_+(G)$ for all $G$ (from definition). There are graphs $G$ for which $\iacr(G) < \acr(G)$~\cite{FPSS12b}. T\'{o}th showed that there are graphs $G$ with  $\acr(G) \leq 0.855 \pcr(G) = \cro(G)$ answering the question from~\cite{PSS08}.
\openq What is the relationship between $\acr$ and $\pcr$?\index{pair crossing number}
\also Odd crossing number, independent algebraic crossing number, monotone crossing number (for monotone variants).
\end{cn}

\entry{Anchored crossing number} See fixed linear crossing number.

\entry{Annulus crossing number} See map crossing number.

\begin{cn}{Bimodal crossing number}\mindex{bimodal crossing number}
\defn The {\em bimodal crossing number} of a directed graph $G$, is the smallest number of crossings in any bimodal drawing of $G$. A drawing is {\em bimodal} if at every vertex all in-coming edges (and thus, all out-going edges) are consecutive.
\reference Buchheim, J{\"u}nger, Menze, Percan~\cite{BJMP06}.
\comments Buchheim, J{\"u}nger, Menze, and Percan~\cite{BJMP06} introduce bimodal drawings as a relaxation of hierarchical drawings with the goal of reducing the number of crossings.
\complexity \NP-complete~\cite{BJMP06}. The embeddability problem is in \P (easy reduction to planarity).
\relations The upward crossing number\index{upward crossing number} is an upper bound on the bimodal crossing number (and they differ, because the upward crossing number is infinite for directed cycles).
\also Upward crossing number.
\end{cn}

\begin{cn}{Bipartite crossing number}\mindex{bipartite crossing number}
\defn The {\em bipartite crossing number}, $\bcr(G)$, of a bipartite graph $G$ is the smallest number of crossings in a straight-line drawing of $G$ between two parallel lines so that the vertices in the same partition lie on the same line.
\reference Harary~\cite{H69}; Watkins~\cite{W70}; Harary, Schwenk~\cite{HS71,HS72}. Also~\cite{C1889}.
\comments Harary develops this crossing number notion without naming it. Watkins called it the {\em special crossing number}; Harary and Schwenk coined {\em bipartite crossing number} and wrote $\nu_2(G)$, May~\cite{M85}, in a paper on circuit layout, calls it the {\em inner crossing number} $\nu^*$\mindex{inner crossing number}. None of these names seem to have stuck; the corresponding optimization problem is now known as the $2$-sided (or $2$-layer) crossing minimization problem (e.g.~\cite{ZB07}). In the $1$-sided crossing minimization problem the order of vertices on one of the two lines is fixed.\footnote{The crossing minimization problem for tanglegrams~\cite{FKP10,WSP12} has a similar flavor; in a tanglegram\index{tanglegram}, the ordering of the vertices in each partition is constrained by a tree.} Hotz~\cite[Section 3.6.3]{H74} discusses an application to circuit layout in which the permutations on either side are restricted by the nature of the circuit. As an extremal question, the bipartite crossing number is even older. In a textbook on algebra from 1889, Chrystal~\cite[p.34]{C1889} asks to verify the bipartite crossing number of $K_{m,n}$ (his value is off by a factor of $2$). Also, see Singmaster~\cite[5.Q.1]{S04x}. The name bipartite crossing number has also been used for $\cro(K_{m,n})$, Zarankiewicz's problem.
\complexity \NP-complete.\footnote{Shahrokhi and Vr{\v{t}}o~\cite{SV99} write ``the \NP-hardness of the problem was proved for multigraphs, but it is widely assumed that it is also \NP-hard for simple graphs''. The multigraph proof is due to Garey and Johnson~\cite{GJ83}. The problem remains \NP-complete for simple graphs as well (thanks to Daniel \v{S}tefankovi\v{c} for help with this proof): by a result of Even and Shiloah~\cite{ES75} the optimum linear arrangement problem is \NP-hard for bipartite graphs; take a bipartite graph $G$ and make each of its vertices the center of a sufficiently large star; in a crossing-minimal bipartite drawing of the resulting graph, the leaves of the star can be assumed to be consecutive; this bipartite drawing encodes a solution to the optimum linear arrangement problem of the original graph $G$, just as in the original proof by Garey and Johnson.} Can be approximated in polynomial time to within a factor of $O(\log^2 n)$~\cite{SSSV01}. The embedding problem is easy, Harary and Schwenk~\cite{HS72} give a complete characterization of graphs with $\bcr(G) = 0$. The $1$-sided crossing minimization problem is \NP-complete~\cite{EMKW86,EW94}, but fixed-parameter tractable~\cite{DW04,KT12}.
\relations $\rcr(G) \leq \bcr(G)$\index{rectilinear crossing number} for all bipartite graphs $G$, and the inequality can be strict (e.g.\ $K_{2,2}$). If $G$ is a $2$-connected, bipartite graph, then $\bcr(G) \geq (m-1)/3$, where $m = |E(G)|$~\cite{KMNT13}.
\values $\bcr(C_{2n}) = n-1$~\cite{HS72}. $\bcr(K_{m,n}) = {m \choose 2} {n \choose 2}$~\cite{C1889,W70}. $\bcr(M_{2,n}) = n-1$, $\bcr(M_{3,n}) = 5n-6$, $\bcr(M_{m,n}) = \Theta(m^2n)$ where $M_{m,n} = P_m \Box P_n$ is the $m \times n$ mesh, and $\bcr(Q_n) = \Theta(4^n)$~\cite{SSSV00}.
\also Radial crossing number, cylindrical crossing number, tile crossing number, bipartite confluent crossing number (under confluent crossing number), upward crossing number. Generalizations include convex $k$-partite crossing number and leveled crossing number (under monotone crossing numbers).
\end{cn}

\entry{Bipartite confluent crossing number} See confluent crossing number.

\entry{Biplanar crossing number} See $k$-planar crossing number.

\begin{cn}{Book crossing number}\mindex{book crossing number}\mindex{k page crossing number@$k$-page crossing number}
\defn A {\em book} with $k$ pages is a branched surface consisting of $k$ half-planes whose boundary lines have been identified (forming the {\em spine}). The {\em book crossing number} for a book with $k$ pages, or {\em $k$-page crossing number}, $\bkcr_k(G)$, of a graph $G$, is the smallest number of crossings in a drawing of $G$ in a book with $k$ pages so that all vertices lie on the spine of the book and every edge lies in a single page. The smallest $k$ for which $\bkcr_k(G) = 0$ is the {\em pagenumber} of $G$.
\reference Nicholson~\cite{N68}; Leclerc and Monjardet~\cite{LM69} (for $\bkcr_2$). Shahrokhi, S{\'y}kora, Sz{\'e}kely, Vr\v{t}o~\cite{SSSV95} (for $\bkcr_k$).
\comments The book crossing number for a single page is the same as the convex crossing number. There are two types of book drawings, {\em combinatorial}, in which edges are not allowed to cross the spine, and {\em topological} in which edges are allowed to cross the spine~\cite[3.1.3.1]{W05}. The book crossing number is restricted to combinatorial drawings, and there is good reason for that, since a topological book crossing number would not add anything new: for a single page, the spine cannot be crossed, so we again get the convex crossing number and for two pages, $k=2$, we would get the standard crossing number as was observed (and proved) by Nicholson~\cite[Appendix]{N68}.\footnote{One has to keep in mind that Nicholson proved this result very early in the history of the crossing number; his primary goal is an aesthetic layout (he restricts edge segments on each page to be drawn like semicircles) which minimizes the number of crossings via a heuristic that modifies the permutation along the spine.} Finally, every graph can be embedded in $3$ pages if we allow a topological embedding.\footnote{This result is due to Atneosen~\cite{A68}. White~\cite[page 59]{W84} gives a very simple proof he attributes to Babai in 1974 (essentially the same proof found later by Bernhart and Kainen~\cite{BK79}).} The spine crossing number is a variant that does allow topological drawings (but counts crossings differently).

Combinatorial drawings in two pages have been called circular~\cite{W05} or cycle~\cite{H02} drawings, so the name circular\index{circular crossing number} or cycle crossing number\index{cycle crossing number} for the crossing number $\bkcr_2$ would not be surprising. More typically, though, $\bkcr_2$ is known as the {\em $2$-page crossing number}\mindex{$2$-page crossing number} or sometimes the {\em (free) linear crossing number\mindex{free linear crossing number}\mindex{linear crossing number}}, e.g.~\cite{MNKF90}.

There are two degrees of freedom in finding a combinatorial book-drawing: finding the best order of vertices along the spine and determining which page each edge is drawn in. We get interesting variants, if we restrict either of these. If one fixes the order of the vertices along the spine, one obtains the {\em fixed linear crossing number}\index{fixed linear crossing number}, discussed in a separate entry. If one assigns each edge to a specific page, one gets what could be called the {\em partitioned book crossing number}\index{partitioned book crossing number}; we treat it as a special case of the convex simultaneous crossing number\index{convex simultaneous crossing number} (see entry for simultaneous crossing number).

If instead of counting crossings, we count edges involved in crossings, we get the book edge crossing number introduced by Bannister, Eppstein, and Simons~\cite{BES13}, see the entry on edge crossing number.

\complexity The problem is interesting even for the special case of embeddings, that is, $\bkcr_k(G) = 0$. Graphs of pagenumber $1$ are the outerplanar graphs which can be recognized in linear time. Graphs of pagenumber $2$ are the planar subgraphs of Hamiltonian graphs which implies that testing $\bkcr_2(G) = 0$ is \NP-complete~\cite{CLTR85}.\footnote{The characterization of pagenumber $2$ graphs is due to Bernhart and Kainen~\cite{BK79}, but also see~\cite{BS84} on the pre-history of that observation.} Testing $\bkcr_k(G) = 0$ for fixed $k \geq 4$ is also \NP-complete, since it is for a given ordering of the vertices on the spine (one can easily construct a gadget that forces a given ordering in a book-embedding); see the entry on the fixed linear crossing number\index{fixed linear crossing number}, which is the variant of the book crossing number in which the order of the vertices is given. As far as we know, the complexity of testing $\bkcr_3(G) = 0$ is open. The only general complexity result about the crossing number version we are aware of is the special case of the convex crossing number\index{convex crossing number}, $k=1$: testing $\bkcr_1(G) \leq m$ is \NP-complete~\cite{MKNF87}. For $k$-almost trees, the computation of $\bkcr_1(G)$ and $\bkcr_2(G)$ is fixed-parameter tractable (with $k$ as the parameter)~\cite{BES13}.
\relations $\bkcr_{k}(G) \leq \bkcr_{k-1}(G)$ (by definition). $\bkcr_k(G) \leq \bkcr_1(G) / k$~\cite{SSSV95}, $\mcro(G) \leq \bkcr_2(G)$\index{monotone crossing number} (from definition)and so $\bkcr_{2k}(G) \geq \cro_k(G)$ (see $k$-planar crossing number), also $\bkcr_1(G) \geq \rcr(G)$\index{rectilinear crossing number} (obvious, since $\bkcr_1$ is the convex crossing number). A crossing lemma is known: $\bkcr_k(G) \geq m^3/(37k^2n^2) - 27kn/37$ for $n = |V|$, $m = |E|$~\cite{SSSV96}.
\values For $\bkcr_1$, see the entry on convex crossing number. $\bkcr_2(K_n) = Z(n)$~\cite{AAFMRS13,AAFMRS13a} (for earlier results, see~\cite{BZ06,dKP12}) and $\bkcr_2(K_{m,n}) \leq Z(m,n)$~\cite{dKP12}, with $Z(n) = X(n)X(n-2)/4$ and $Z(m,n) = X(m)X(n)$, where $X(n) = \lfloor n/2 \rfloor \lfloor (n-1)/2\rfloor$. Buchheim and Zheng~\cite{BZ06} calculate $\bkcr_2$ for several small graphs. Asymptotic results include $\lim_{n \rightarrow \infty} \bkcr_2(K_{m,n})/Z(m,n) \geq 0.9253$~\cite{dKP12}. Faria, de Figueiredo, Richter and Vr{\v{t}}o~\cite{FdFRV13} give upper bounds on $\bkcr_2(Q_n)$ (improving work by Madej~\cite{M91}). Satsangi, Srivastava, Srivastava~\cite{SSS13} show (computationally) that $\bkcr_2(K_{1,4,n}) = n(n-2)$ for $2 \leq n \leq 15$. For values of $\bkcr_k(K_n)$ for $k \geq 3$ and small values of $n$ as well as asymptotic bounds, see~\cite{dKPS13}. For values of $\bkcr_k(K_{k+1,n})$ for $3 \leq k \leq 6$, asymptotic results for $\bkcr_k(K_{k+1,n})$, and upper bounds on $\bkcr_k(K_{m,n})$ see~\cite{dKPS12b}.
\openq deKlerk and Pasechnik~\cite{dKP12} conjecture $\bkcr_2(K_{m,n}) = Z(m,n)$. Yannakakis~\cite{Y86,Y89} proved that every planar graph has pagenumber at most $4$, but his example of a planar graph that needs $4$ pages announced in~\cite{Y86} is not in~\cite{Y89}. According to Kainen~\cite{K11}, the question whether $\bkcr_3(G) = 0$ for all planar graphs $G$ is still open. As a weaker conjecture he suggests $\limsup_{\cro(G) = 0} \bkcr_3(G)/\log |V(G)| = 0$. DeKlerk, Pasechnik, and Salazar~\cite{dKPS12b} ask whether $\gamma(k) : = \lim_{m,n \rightarrow \infty} \cro_{2k}(K_{m,n})/$ $\bkcr_k(K_{m,n})$ goes to $1$ as $k$ goes to infinity? Faria, de Figueiredo, Richter and Vr{\v{t}}o~\cite{FdFRV13} ask whether $\bkcr_2(Q_n) \leq \rcr(Q_n)$; this is not true for all graphs: as they point out, a non-Hamiltonian planar triangulation $G$ satisfies $\bkcr_2(G) > 0 = \rcr(G)$. Satsangi, Srivastava, Srivastava~\cite{SSS13} conjecture that $\bkcr_2(K_{1,4,n}) = n(n-2)$ for all $n$; they also make some conjectures on the pagenumber of certain graph families, based on computational evidence.
\also Convex crossing number, fixed linear crossing number, convex simultaneous crossing number (under simultaneous crossing number), spine crossing number, anchored crossing number, book edge crossing number (under edge crossing number).
\end{cn}

\entry{Book edge crossing number} See edge crossing number.

\entry{Circular crossing number} See convex crossing number.

\entry{Circular $k$-partite crossing number} See convex crossing number.

\entry{Clockwise crossing number} See cyclic level crossing number.

\begin{cn}{Confluent crossing number}\mindex{confluent crossing number}
\defn A {\em confluent drawing} (sometimes known as a train track) consists of branches (simple curves with two connection points) and switches (homeomorphs of the symbol $\prec$, so three connection points), and nodes. Each of the three connection points of a switch is incident to a node, or to the connection point of exactly one branch or one switch. Each connection point of a branch is incident to a connection point of a switch or a node. The drawing is smooth at connection points and the only crossings allowed are crossings between branches. A confluent drawing represents a graph $G = (V,E)$ as follows: $V$ is the set of nodes of the drawing, and an edge in $E$ corresponds to a smooth curve connecting its endpoints (such a curve cannot make a sharp turn between the upward and the downward branch of the $\prec$) without turning around. Note that a single branch or switch can carry many edges. The {\em confluent crossing number} of a graph $G$ is the smallest number of crossings required in a confluent drawing of $G$.
\reference Based on Eppstein, Goodrich, Meng~\cite{EGM07}, also Newberry\cite{N89}.
\comments Confluent drawings were introduced by Dickerson, Eppstein, Goodrich, and Meng~\cite{DEGM05} to reduce the number of crossings (which they do dramatically) while emphasizing the connectivity structure visually. A confluent drawing looks like a train track and track crossing number would be a good alternative name. Eppstein, Goodrich, and Meng\cite{EGM07} define this crossing number implicitly as a crossing minimization problem. They restrict themselves to the special case of two-layered drawings where $G$ is bipartite (each partition being a layer) and distinguish between various levels of depth. So, in effect, they consider a {\em bipartite confluent crossing number}\mindex{bipartite confluent crossing number}. One could consider variants in which switches are also counted as crossings (see Metro-line crossing number\index{Metro-line crossing number}). Newberry~\cite{N89} earlier introduced the technique of edge clustering for layered drawings of directed graphs with the same goal of reducing the total number of crossings. Edges that share the same sources and targets can be bundled (or concentrated) into {\em edge concentration nodes} (which require new levels).
\complexity Open, even the special case of testing whether a graph has a confluent embedding (no crossings) is not known to be \NP-hard (although it is known to lie in \NP~\cite{HPSS07}).
\values Complete and complete bipartite graphs have confluent crossing number $0$, see the crossing-free confluent drawing of $K_5$ in the margin.
\marginpar{
\begin{pspicture}(0,0)(60,40)
\cnode*(0,30){1}{a1}
\cnode*(15,30){1}{a2}
\cnode*(30,30){1}{a3}
\cnode*(45,30){1}{a4}
\cnode*(60,30){1}{a5}

\pnode(7.5,10){m1}
\pnode(22.5,10){m2}
\pnode(37.5,10){m3}
\pnode(52.5,10){m4}

\ncline[linewidth=0.25]{m1}{m4}
\nccurve[linewidth = 0.3,angleA=270,angleB=180]{a1}{m1}
\nccurve[linewidth = 0.3,angleB=270]{m1}{a2} \nccurve[linewidth = 0.3,angleA=270,angleB=180]{a2}{m2}
\nccurve[linewidth = 0.3,angleB=270]{m2}{a3} \nccurve[linewidth = 0.3,angleA=270,angleB=180]{a3}{m3}
\nccurve[linewidth = 0.3,angleB=270]{m3}{a4} \nccurve[linewidth = 0.3,angleA=270,angleB=180]{a4}{m4}
\nccurve[linewidth = 0.3,angleB=270]{m4}{a5}
\end{pspicture}
}
\also Metro-line crossing number.
\end{cn}

\begin{cn}{Constrained crossing number}\mindex{constrained crossing number}
\defn A {\em partially embedded graph} is a graph $G = (V,E)$ with a subgraph $H \subseteq G$ and an embedding ${\cal H}$ of $H$ in the plane. The {\em constrained crossing number} of $G$ given ${\cal H}$ is the smallest number of crossings in any drawing of $G$ that contains ${\cal H}$.
\reference Mutzel, Ziegler~\cite{MZ99, MZ99b}.
\comments Mutzel, Ziegler defined a more restricted variant: they required $H$ to be a connected graph with vertex set $V$. In that case, ${\cal H}$ can be described completely by its rotation system. Recent results on partially embedded graphs suggest that the more general point of view taken here is justified.
\complexity \NP-complete (since crossing number is a special case); the restricted case defined by Mutzel and Ziegler is also \NP-complete since fixed linear crossing number\index{fixed linear crossing number} is a special case. Testing whether there is an embedding of $G$ containing ${\cal H}$ is in linear time~\cite{ABFJKPR10}.
\openq Is the constrained crossing number fixed-parameter tractable for parameter $k = |E(G)| - |E(H)|$?
\also Fixed linear crossing number, crossing number of graphs with rotation, map crossing number, wire crossing number.
\end{cn}


\begin{cn}{Convex crossing number}\mindex{convex crossing number}
\defn The {\em convex crossing number} of a graph $G$, $\bkcr_1(G)$, is the smallest number of crossings in a drawing of $G$ in which all vertices of $G$ lie on the boundary of a convex set and edges have to lie within the convex set. If $G$ is a $k$-partite graph we can require that all vertices belonging to a particular partition occur consecutively on the boundary. Call this variant the {\em convex $k$-partite crossing number}\mindex{convex $k$-partite crossing number} of $G$.
\reference M\"{a}kinen~\cite{M88}, Kainen~\cite{K90} (with caveat, see comments). Riskin~\cite{R07}.
\comments  The convex crossing number is the same as $\bkcr_1$, the {\em $1$-page book crossing number}\mindex{$1$-page crossing number}; other names include {\em outerplanar crossing number\mindex{outerplanar crossing number}}~\cite{SSSV95} and {\em circular crossing number\mindex{circular crossing number}}~\cite{ST99}. Extremal problems that, in effect, ask for the calculation of the convex crossing number for certain graphs are even older: an exercise in an algebra textbook published in 1889 asks to verify the number of crossings in a convex drawing of $K_{n}$ (Chrystal~\cite[p.34]{C1889}). See Singmaster~\cite[5.Q.1]{S04x} for related puzzles.
M\"{a}kinen~\cite{M88} mentions the possibility of minimizing edge crossings in convex drawings, but immediately
dismisses it, preferring circular dilation to optimize drawings. Kainen~\cite{K90} introduced the {\em local outerplanar crossing number}\mindex{local outerplanar crossing number}, which he abbreviated as $\mathit{locr}(G)$, and which we would call the {\em local convex crossing number}\mindex{local convex crossing number}), in which we try to minimize the largest number of crossings along any edge; drawings with local convex crossing number at most $1$ have been called {\em outer $1$-planar}~\cite{E86,ABBGHNR13}.\footnote{Eggleton~\cite{E86} introduced a degenerate version of outer $1$-planarity, see the discussion under the entry for local crossing number.} Riskin introduced the convex $k$-partite crossing number\mindex{convex $k$-partite crossing number} as the circular $k$-partite crossing number\index{circular k partite crossing number@circular $k$-partite crossing number}.\footnote{There really is no reason to restrict this crossing number to $k$-partite graphs, it also makes sense if we allow crossings within each partition. Arguably, this is exactly the crossing number variant discussed by Bronfenbrenner~\cite{B45} in a 1945 sociology paper unearthed by David Eppstein~\cite{E13}.} For $k=2$ it equals the bipartite crossing number\index{bipartite crossing number}, for $k= |V|$ it reverts to the convex crossing number. For a version maximizing the number of crossings, see the maximum convex rectilinear crossing number\index{maximum convex rectilinear crossing number} (under maximum rectilinear crossing number). One could also imagine allowing multiple layers of points in convex position; for the special case of rectilinear drawings of the complete graph, this has been studied in~\cite{L13}; that approach could also be viewed as a refinement of the rectilinear crossing number\index{rectilinear crossing number}.
\complexity \NP-complete~\cite{MKNF87}. Testing whether the local convex crossing number is at most $1$ is in linear time~\cite{ABBGHNR13}.\index{local convex crossing number}
\relations $\bkcr_1(G) \geq \rcr(G)$\index{rectilinear crossing number} for all graphs $G$ (from definition). There is a crossing lemma, $\bkcr_1(G) \geq m^3/(27n^2)$~\cite{SSSV04}.
\values Obviously, $\bkcr_1(K_n) = {n \choose 4}$~\cite[p.34]{C1889}. For results on the convex $k$-partite crossing number of $K_{m,n}$ see Riskin's papers~\cite{R03,R07b}, for results on $K_{n,n, \ldots, n}$, see~\cite{FHSV05}. Let $M_{m,n} = P_m \Box P_n$ denote the $m \times n$ mesh. $\bkcr_1(M_{3,n}) = 2n-3$ if $n$ even and $2n-4$ otherwise, $n \geq 3$~\cite{FHSV05},  $\bkcr_1(M_{4,n}) = 4(n-2)$ for $n \geq 2$~\cite{HSM10}. Asymptotically, $\bkcr_1(M_{n,n}) = \Omega(n^2 \log n)$~\cite{SSSV04}. For Halin graphs, see~\cite{FHSV05}, for circulant graphs see~\cite{HSM10}, and for the cone graph $C_n * \overline{K}_2$ see~\cite{K11}.
\also Bipartite crossing number, tile crossing number, disk crossing number (under map crossing numbers), convex simultaneous crossing number.
\end{cn}

\entry{Convex $k$-partite crossing number} See convex crossing number.

\entry{Convex maximum rectilinear crossing number} See maximum rectilinear crossing number.

\entry{Convex simultaneous crossing number} See simultaneous crossing number.

\entry{Cross index} See local crossing number.

\entry{Crossing edge number} See edge crossing number.

\begin{cn}{Crossing number}\mindex{crossing number}\mindex{surface crossing number}
\defn The {\em crossing number} of $G$, $\cro(G)$, is the smallest number of crossings in any drawing of $G$. We write $\cro_{\Sigma}(G)$ for the crossing number of $G$ on surface $\Sigma$; $\cro_{S_g}$ is also known as the {\em genus $g$ crossing number}\mindex{genus g crossing number@genus $g$ crossing number}, $\cro_{S_1}$ is the {\em toroidal crossing number}\mindex{toroidal crossing number}, $\cro_{N_1}$ is the {\em projective plane crossing number}\mindex{projective plane crossing number} and $\cro_{N_2}$ is the {\em Klein bottle crossing number}\mindex{Klein bottle crossing number}. If the graph is equipped with a rotation (embedding) scheme $\rho$, we write $\cro_{\Sigma}(G,\rho)$\mindex{rotational crossing number} for the crossing number of the graph with the prescribed rotation (embedding) scheme $\rho$.
\reference Tur\'{a}n~\cite{T77}, Harary and Hill~\cite{HH63}, also Harary~\cite{H64,H65}.
\comments For a detailed account of the early history of the crossing number, see Beineke and Wilson's ``The Early History of the Brick Factory problem''~\cite{BW10}, but also see Remark~\ref{rem:FCMS}. Influenced by Turan's problem~\cite{T77}, research during the initial phase (1950s) focussed on the crossing number of the complete bipartite graph (Zarankiewicz~\cite{Z53}, Urbanik~\cite{U55}) and in the 1960s expanded to include investigation of complete graphs (e.g. Guy~\cite{G60}, who credits Anthony Hill and C.A.~Rogers, and writes that Erd\H{o}s claimed to have been thinking about the problem for $20$ years; also Saaty~\cite{S64}).  As far as we can tell, the first paper defining the crossing number\index{crossing number} for arbitrary graphs is due to Harary and Hill in 1963~\cite{HH63}. The toroidal crossing number\index{toroidal crossing number} was introduced in~\cite{GJ69,K69}, and the Klein bottle crossing number\index{Klein bottle crossing number} together with general surface crossing numbers in~\cite{K69} (also~\cite{K72}).
\complexity \NP-complete~\cite{GJ83}, remains \NP-complete for nearly planar graphs~\cite{CM10}, cubic graphs~\cite{H06} and if the drawing of the graph is restricted by a given rotation (embedding) system $\rho$~\cite{PSS09d}. Approximating the crossing number to within a constant factor (even for cubic graphs) is \NP-complete~\cite{C13}, but it can be approximated to within a polynomial bound for graphs of bounded degree~\cite{C11,CS13}. The embedding problem $\cro_{\Sigma}(G) = 0$ can be solved in linear time for any (compact orientable or non-orientable) surface $\Sigma$~\cite{M99}. The surface crossing number problem, $\cro_{\Sigma}(G)$, remains \NP-complete for all surfaces $\Sigma$ (via an easy reduction from the planar case). Testing $\cro(G) \leq k$ can be decided in time $O(f(k) n)$, that is, the problem is fixed-parameter tractable~\cite{G01,KR07}.

\relations $\cro(G) > 1024/31827 m^3/n^2$ for $m > 4n$~\cite{PRTT06}.\footnote{The fact that $\cro(G) = \Omega(m^3/n^2)$ for $m > 4n$ is known as the {\em crossing lemma}. The original versions (with smaller constants) are due to Ajtai,Chv{\'a}tal, Newborn, Szemer{\'e}di~\cite{ACNS82} and Leighton~\cite{L83}. A recent manuscript by Ackerman~\cite{A13b} claims an improvement to $\cro(G) > 0.0345 m^3/n^2$ for $m \geq 6.95n$.} For $\Sigma \in \{S_g, N_g\}$ we have $\cro_{\Sigma}(G) = \Omega(m^3/n^2)$ if $0 \leq g < n^2/m$ and $\cro_{\Sigma}(G) = \Omega(m^2/g)$ if $n^2/m \leq g \leq m/64$~\cite{SSSV96b}. Asymptotically, $\cro(G) = O(g(\cro_{S_g}(G)+n))$ for graphs of bounded degree as long as $g = o(n)$~\cite{DV12}. If $\cro_{\Sigma}(G) = 0$, then $\cro(G) \leq c_{\Sigma} \Delta n$, where $\Delta$ is the maximum degree of $G$~\cite{BPT06}, for an algorithmic view of this result, see~\cite{CHS14}. The behavior of the sequence $\cro_{S_0}(G), \cro_{S_1}(G), \cro_{S_2}(G), \ldots$ (and similarly for non-orientable surfaces) has been studied by \v{S}ir\'{a}\v{n} and others, see~\cite{MC12} for a recent survey and results.

\values The {\bfseries planar} crossing number\index{crossing number} of $K_n$ is at most $Z(n) = X(n)X(n-2)/4$, where $X(n) = \lfloor n/2 \rfloor \lfloor (n-1)/2\rfloor$~\cite{G60,BK64}. Guy's, or Harary and Hill's, conjecture states that $\cro(K_n) = Z(n)$~\cite{HH63,BW10}; the conjecture is known to be true for $n \leq 12$~\cite{PR07}; for a strengthened version of the conjecture, see~\cite{BFK13}. It is known that $\cro(K_n) > 0.8594 Z(n)$ for sufficiently large $n$~\cite{dKPS07}.\footnote{Thanks to the referee for pointing this out; to obtain this result one needs to combine the result on $\cro(K_{n,m})$ from \cite{dKPS07} with the main theorem from~\cite{RT97} discussed below.}
The crossing number of $K_{m,n}$ is conjectured to be given by Zarankiewicz's function $Z(m,n) = X(m) X(n)$, this is known as Zarankiewicz's conjecture. As in the case for complete graphs, the upper bound $\cro(K_{m,n}) \leq Z(m,n)$ is easy, but the lower bound is hard. The conjecture is known to be true for $n \leq 6$~\cite{K70} and $n \leq 8, m \leq 10$~\cite{W93}. $\cro(K_{7,n}) \geq 2.203 n^2 - 4.5n > 0.979 Z(7,n)$~\cite{DV13}, building on~\cite{dKMPRS06}. $\cro(K_{m,n}) > 0.8594 Z(m,n)$ for $m \geq 9$ and $n$ sufficiently large~\cite{dKPS07}. For every $m$ there is an $N(m)$ so that if $\cro(K_{m,n}) = Z(m,n)$ for all $n \leq N(m)$, then $\cro(K_{m,n}) = Z(m,n)$ for all $n$~\cite{CRS13}.
The conjectures for complete and complete bipartite graphs are related: $\lim_{n\rightarrow \infty} \cro(K_n)/Z(n) \geq \lim_{n\rightarrow \infty} \cro(K_{n,n})/Z(n,n)$~\cite{RT97}, so asymptotic improvements on $\cro(K_{m,n})$ lead to corresponding improvements on $\cro(K_n)$.\footnote{Apparently Sz{\'e}kely phrases this as ``If Zarankiewicz's conjecture is asymptotically X\% true, then the Harary-Hill conjecture is also asymptotically X\% true'', thanks to one of the referees for supplying that quote.}
$\cro(K_{1,3,n}) = Z(4,n) + \lceil n/2 \rceil$ and $\cro(K_{2,3,n}) = Z(5,n)+n$~\cite{A86}, $\cro(K_{1,4,n}) = n(n-1)$~\cite{H08,HZ08}.\footnote{There are many further results for (planar) crossing numbers of complete $k$-partite graphs, hypercubes, Cartesian (and Kronecker) products of cycles, paths, and stars and other families of graphs; unfortunately, there does not seem to be an English language survey collecting these results, but many of them can be found in Vr{\v{t}}o's bibliography~\cite{Vx}.} For the {\bfseries projective plane}\index{projective plane crossing number}, $\cro_{N_1}(K_n)$ is known up to $n\leq 10$ and there are asymptotic bounds: $(41/273){n \choose 4} \leq \cro_{N_1}(K_n) \leq (13/16)Z(n)$ for $n \geq 15$~\cite{K69}.\footnote{There do not seem to be any newer results on the projective plane crossing number of complete graphs than this result from 1969.} It is known that $\cro_{N_1}(K_{4,n}) = \lceil n/3\rceil (2n-3(1+\lceil n/3\rceil))$~\cite{H05}. Also, $\cro_{N_1}(C_3 \times C_n) = n-1$ for $n \geq 5$ and $\cro_{N_1}(C_3 \times C_4) = 2$~\cite{R93}. For the {\bfseries torus}\index{toroidal crossing number}, $\cro_{S_1}(K_n)$ is known for $n \leq 10$ and $\cro_{S_1}(K_{m,n})$ for $m,n \leq 6$~\cite{GJS68}. Also, $\cro_{S_1}(K_{3,n}) = \lceil (n-3)^2/12 \rceil$~\cite{GJ69} and  $\cro_{S_1}(K_{4,n}) = \lfloor n/4 \rfloor (2n-4(1+\lfloor n/4 \rfloor ))$~\cite{H09}. There are asymptotic bounds for $\cro_{S_1}(K_{m,n})$~\cite{GJ69}.
For the {\bfseries Klein bottle}\index{Klein bottle crossing number}, $\cro_{N_2}(K_n)$ is known for $n\leq 9$~\cite{K69} and there are asymptotic bounds: $(1/14){n \choose 4} \leq \cro_{N_2}(K_n) < (59/216) {(n-1) \choose 4}$ for $n \geq 16$~\cite{K78}. $\cro_{N_2}(K_{m,n})$ is known for $3 \leq m \leq 6$ and $n \leq N(m)$ with $N(3) = 12$, $N(4) = 8$, $N(5) = N(6) = 6$; for these ranges $\cro_{N_2}(K_{m,n}) = \cro_{S_1}(K_{m,n})$~\cite{K75}. $\cro_{N_2}(C_m \times C_n)$ is known for $m \leq 6$~\cite{R01} and for sufficiently large $m$ and $n$~\cite{JS03}\footnote{See Riskin's MathSciNet review MR1974148 of that paper.}.

Exact values of $\cro_{\Sigma}(K_{3,n})$ are known for all surfaces $\Sigma$~\cite{RS96}, and there are lower and upper bounds on
$\cro_{\Sigma}(K_n)$, $\cro_{\Sigma}(K_{n,m})$, and $\cro_{\Sigma}(Q_n)$~\cite{SSSV96a,SSSV96b}.
\openq There is a well-known conjecture by Harary, Kainen and Schwenk~\cite{HKS73} that $\cro(C_m \times C_n) = n(m-2)$ for $n \geq m \geq 3$; the conjecture is known to be true for $3 \leq m \leq 7$~\cite{RB78,BR80,KRS96,RS01,AR04}, and for $n \geq m(m+1)$, $m \geq 3$~\cite{GS04}; for surveys predating the more recent developments ($6 \leq m \leq 7$, and $n \geq m(m+1)$), see~\cite{R96,SSSV97}. It is also known that
for every $m$ there is a $c_m \geq 0$ so that $\cro(C_m \times C_n) = n(m-2) - c_m$ for $n \geq 3$~\cite{PR04b}. DeVos, Mohar, and {\v{S}}{\'a}mal asked whether it is true that in any $\cro$-minimal drawing of the disjoint union of two graphs $G_1$ and $G_2$ on a surface $\Sigma$, the drawings of $G_1$ and $G_2$ are disjoint? Trivially true for plane, and also known for projective plane~\cite{DMS08}. B{\"o}r{\"o}czky, Pach, and T{\'o}th~\cite{BPT06} ask whether $\cro(G) = O(g\Delta n)$, where $g$ is the genus of $G$, and $\Delta$ its maximum degree (this is known to be true of the torus~\cite{PT06a}). Shahrokhi, Sz{\'e}kely, and S{\'y}kora~\cite{SSSV96b} conjecture that $\cro_{\Sigma}(K_n) = O(n^4/g)$, where $\Sigma \in \{S_g, N_g\}$.

\also Stable crossing number.
\end{cn}

\begin{cn}{Crossing number of abstract topological graph}\mindex{crossing number of abstract topological graph}
\defn A graph $G$ with a symmetric relation $R$ over $E(G)$ is called an {\em abstract topological graph} or {\em AT-graph}. A drawing $D$ is a {\em weak realization} of $(G,R)$ if every pair of edges $(e,f)$ that cross in $D$ belongs to $R$. The {\em crossing number} of $(G,R)$, $\cro(G,R)$, is the smallest number of crossings in a weak realization of $(G,R)$. If there is no weak realization of $(G,R)$ we let $\cro(G,R) = \infty$.
\reference Kratochv\'{\i}l~\cite{K98}.
\comments Kratochv\'{\i}l introduced the crossing number $\mathrm{cr}_{at}(G,R)$ of an abstract topological graph $(G,R)$ in his study of string graphs. Intersection graph theory studies graphs $(G,R)$ which have weak realizations for restricted $R$. Trivially, if $R$ contains no edges, then $G$ has a linear number of edges (since it is planar). Linear bounds on $|E(G)|$ are also known if $R$ excludes a complete bipartite~\cite{PPST05} or tripartite~\cite{TT07} graph.
This crossing number can be viewed as a special case of the weighted crossing number (weights being restricted to $1$ and $\infty$).
\complexity \NP-complete~\cite{SSS08}.
\relations $\cro(G) \leq \cro(G,R)$ (by definition). There are abstract topological graphs $(G,R)$ for which $\cro(G,R) \geq 2^{c n}$ for some $c>0$~\cite{K98,KM91}, where $n = |V(G)|$. If $\cro(G,R) < \infty$, then $\cro(G,R) \leq m 2^n$~\cite{SSS08}, where $m = |E(G)|$ and $n = |V(G)|$.
%\values
\openq Kratochv\'{\i}l~\cite{K98} conjectured that in any crossing minimal weak realization of $(G,R)$ any edge which is involved in crossings is crossed by some edge exactly once. Graphs $G$ which are weakly realizable with an $R$ excluding the complete graph $K_k$ are known as {\em $k$-quasi-planar}\index{k quasi planar@$k$-quasi-planar}. It is open whether $|E(G)|$ is linear for $k$-quasi-planar graphs in general, though it is known for $k \leq 4$~\cite{FPS13}.
\also Weighted crossing number.
\end{cn}

\entry{Crossing parameter} See local crossing number.

\begin{cn}{Cyclic level crossing number}\mindex{cyclic level crossing number}
\defn A {\em cyclic $k$-level graph} $G = (V,E,\ell)$ is a directed graph $(V,E)$ with a {\em leveling} $\ell$, a mapping from $V$ to $\{1,\ldots,k\}$ which assigns a level $\ell(u)$ to each vertex $u$. Fix $k$ rays, all starting at the origin, and number them $1$ through $k$ in clockwise order. A {\em cyclic} drawing of a cyclic $k$-level graph is a drawing in which a vertex $u$ is placed on ray $\ell(u)$, and a directed edge $(u,v)$ is drawn in the clockwise wedge between rays $\ell(u)$ and $\ell(v)$ so that the edge crosses all rays starting at the origin (not just the $k$ rays we chose) at most once. The {\em cyclic level crossing number} of a cyclic $k$-level graph is the smallest number of crossings in a cyclic drawing of the graph.
\reference Based on Bachmaier, Brandenburg, Brunner, H{\"u}bner~\cite{BBBH11}.
\comments The idea of realizing a leveled graph in a cyclic drawing can be found in a paper by Sugiyama, Tagawa and Toda~\cite{STT81}, where cyclic $k$-level graphs are introduced in an appendix under the name {\em recurrent hierarchies}. The crossing minimization problem for cyclic $k$-level graphs is studied by Bachmaier, Brandenburg, Brunner, H{\"u}bner~\cite{BBBH11}, without introducing a name for the corresponding crossing number. The authors also refer to a 2009 master's thesis by H{\"u}bner, which is entitled ``A global approach on crossing minimization in hierarchical and cyclic layouts of leveled graphs''. A cyclic layout could be visualized in a non-cyclic way by repeating one of the layers at the beginning and end; this is what Bertin~\cite[Figure 4, p.109]{B10} does in his visualization of a tripartite perfect matching in which the order of vertices is fixed in each partition; he uses the number of crossings between two layers as a measure of similarity: ``The nearer the order between the columns, the less numerous are the intersections.''.

One could also consider a {\em clockwise crossing number}\index{clockwise crossing number}, in which a directed graph $G = (V,E)$ is given, and the problem is to find a leveling $\ell$ that minimizes the cyclic level crossing number of $(V,E,\ell)$. This clockwise crossing number is to the cyclic level crossing number what the upward crossing number\index{upward crossing number} is to the leveled crossing number\index{leveled crossing number}.
\complexity \NP-complete, since the bipartite crossing number is a special case. The embedding problem can be solved in quadratic time~\cite{BBBF09}.
%\relations
%\values
%\openq \also Leveled crossing number (under monotone crossing numbers), $k$-layer crossing number.
\end{cn}


\begin{cn}{Cylindrical crossing number}\mindex{cylindrical crossing number}
\defn A {\em cylindrical drawing} of a graph $G$ is a drawing in which all vertices of $G$ lie on two concentric circles, and no edge crosses a circle. The {\em cylindrical crossing number} of $G$, $\cro_{\circledcirc}(G)$, is the smallest number of crossings in a cylindrical drawing of $G$.
\reference {\'A}brego, Aichholzer, Fern{\'a}ndez-Merchant, Ramos, and Salazar~\cite{AAFMRS13a}, based on earlier suggestion by Richter and Thomassen~\cite{RT97}.
\comments For bipartite graphs one can require that vertices in the same partition lie on the same circle, and that the inner face of the smaller circle and the outer face of the larger circle do not contain any edges; in that case one would obtain a special case of the radial crossing number with two levels. This type of bipartite cylindrical drawing was introduced in Richter and Thomassen~\cite{RT97} as a stepping stone to cylindrical drawings of $K_n$, which is a class of drawings realizing the conjectured minimal crossing number $Z(n)$ of $K_n$, where $Z(n) = X(n)X(n-2)/4$, and $X(n) = \lfloor n/2 \rfloor \lfloor (n-1)/2\rfloor$. If in addition to requiring the inner and outer face to be empty, we fix the cyclic order of the vertices on the concentric circles, we obtain the annulus crossing number\index{annulus crossing number}. The cylindrical crossing number for general (non-bipartite) graphs was introduced in~\cite{AAFMRS13a}.
\complexity Open.
%\relations
\values $\cro_{\circledcirc}(K_n) = Z(n)$~\cite{AAFMRS13a}.
%\openq
\also Radial crossing number, annulus crossing number (under map crossing number).
\end{cn}

\begin{cn}{Degenerate crossing number}\mindex{degenerate crossing number}
\defn The {\em degenerate crossing number} of a drawing $D$ of a graph $G$ is the number of points in which edges cross each other (that is, we count each point at which crossings occur only once, not ${k \choose 2}$ times for $k$ edges passing through it); recall that edges are not allowed to touch, and may not cross themselves. The {\em degenerate crossing number} of a graph $G$, $\dcr(G)$, is the smallest number of crossing points in a drawing of $G$. If we minimize over simple drawings only (each pair of edges crosses at most once), we obtain the {\em simple degenerate crossing number}\mindex{simple degenerate crossing number}, $\dcr^*(G)$.
\reference Pach, T\'{o}th~\cite{PT09}.
\comments Pach and T\'{o}th~\cite{PT09} credit G\"{u}nter Rote and M. Sharir with asking ``what happens if multiple crossings are counted only {\em once}''. If we allow self-crossings we get the genus crossing number.
Some papers use the term degenerate crossing number for $\dcr^*$~\cite{AP13}.
The definition of $\dcr^*$ is ambiguous. It is not clear whether the definition by Pach and T\'{o}th~\cite{PT09} is aiming for crossing-simple\index{crossing-simple} or intersection-simple\index{intersection-simple}. There is a difference between the two, for example the graph shown in the margin
\marginpar{
\psset{unit=1.2pt}
\begin{pspicture}(0,10)(60,20)
\cnode*(0,0){1pt}{v1}
\cnode*(60,0){1pt}{v2}
\cnode*(60,20){1pt}{v3}
\cnode*(0,20){1pt}{v4}

\cnode*(30,15){1pt}{v5}
\cnode*(30,10){1pt}{v6}
\cnode*(30,5){1pt}{v7}

\ncline[linewidth=0.3]{v1}{v2}
\ncline[linewidth=0.3]{v2}{v3}
\ncline[linewidth=0.3]{v3}{v4}
\ncline[linewidth=0.3]{v4}{v1}
\ncline[linewidth=0.3]{v5}{v7}

\ncline[linewidth=0.3]{v3}{v5}
\ncline[linewidth=0.3]{v2}{v7}
\nccurve[linewidth=0.3,angleA=0, angleB=135]{v6}{v2}

\nccurve[linewidth=0.3,angleA=-45,angleB=180]{v4}{v7}
\nccurve[linewidth=0.3,angleA=45,angleB=180]{v1}{v5}
\nccurve[linewidth=0.3,angleA=-70,angleB=180,ncurv=0.85]{v4}{v6}
\end{pspicture}
}
has crossing-simple\index{crossing-simple} degenerate crossing number $1$, but it requires at least two crossings, if adjacent edges are not allowed to cross.
\complexity Open.
\relations $\gcr(G) \leq \dcr(G) \leq \dcr^*(G) \leq \cro(G)$ by definition. There are examples with $\dcr(G) < \dcr^*(G)$~\cite{PT09}. There is a crossing lemma for the simple version, $\dcr^*(G) \geq c m^4/n^4$ if $m \geq 4n$, while, on the other hand, $\dcr(G) < m$, where $m = |E(G)|$, $n = |V(G)|$~\cite{PT09}. Ackerman and Pinchasi have announced a stronger crossing lemma: $\dcr^*(G) \geq c \cdot m^3/n^2$ for $m \geq 4n$~\cite{AP13}, which is asymptotically optimal.
\values Pach and T\'{o}th~\cite{PT09} claim that $\dcr(K_{5,5}) \leq 15$, comparing it to $\cro(K_{5,5}) = 16$.
\also Genus crossing number, triple crossing number.
\end{cn}

\entry{Degenerate local crossing number} See local crossing number.

\entry{Diagonal crossing number} See joint crossing numbers.

\entry{Directed crossing number} See upward crossing number.

\entry{Disk crossing number} See map crossing number.

\begin{cn}{Edge crossing number}\mindex{edge crossing number}
\defn The {\em edge crossing number} of a drawing $D$ of a graph $G$ is the number of edges involved in crossings in $D$. The {\em edge crossing number} of $G$, $\ecr(G)$, is the smallest edge crossing number of any drawing of $G$. The {\em rectilinear edge crossing number}\mindex{rectilinear edge crossing number} of $G$, $\recr(G)$, is the smallest edge crossing number of any rectilinear drawing of $G$. We can also define maximum variants. The {\em book edge crossing number}\mindex{book edge crossing number} of $G$ is the smallest edge crossing number of any $k$-page book drawing of $G$.
\reference Based on Ishiguro~\cite{I08}, Gange, Stuckey, Marriott~\cite{GSM10}, Bannister, Eppstein, Simons~\cite{BES13}.
\comments {\em Crossing edge number}\index{crossing edge number} may be a better name to avoid confusion with the standard crossing number (which is sometimes called edge crossing number). However, the term crossing edge number has also been used for skewness\index{skewness}~\cite{GH99} with which $\ecr$ could be easily confused. The skewness of $G$, $\sk(G)$, is the smallest number of edges whose removal make a graph planar, while $\ecr(G)$ minimizes the number of edges involved in crossings. By definition, $\sk(G) \leq \ecr(G)$ and it is easy to construct graphs $G$ for which $\sk(G) = 1$ and $\ecr(G)$ is arbitrarily large.\footnote{One could imagine the following cover variant of the edge crossing number: let the {\em edge crossing cover number}\mindex{edge crossing cover number}, $\rho'(G)$ be the smallest number of edges for which there is a drawing of $G$ in which every crossing lies on one of the edges. Then, by definition, $\sk(G) \leq \rho'(G) \leq \ecr(G)$. While this particular variant has not been defined, Albertson~\cite{A08} did define the {\em crossing cover number}\mindex{crossing cover number}, $\rho(G)$, which is the smallest number of vertices so that in some drawing of $G$ every crossing lies on an edge incident to one of the vertices. These parameters are cover numbers rather than crossing numbers though, so we do not pursue them here.} Gange, Stuckey, Marriott~\cite{GSM10}, in passing, mention the possibility of minimizing the number of edges involved in crossings. Ishiguro~\cite{I08} defines a notion he calls {\em minimum non-crossing edge number}\index{minimum non-crossing edge number}\index{non-crossing edge number}, $\nce(G)$, which, in our terminology, is $|E(G)|- \maxrecr(G)$. Maybe the most explicit definition so far is in the paper by Bannister, Eppstein, and Simons~\cite{BES13}, defining edge crossing numbers for $1$-page and $2$-page embeddings, which they denote as $\mathrm{cre}_1(G)$ and $\mathrm{cre}_2(G)$.
 The edge crossing number, unlike the skewness of a graph, can be made to fit our general notion of crossing number: $\sum_{e \in E} \max_{f \in E} \pcr(e,f)$, where $\pcr(e,f) = 1$ if and only if $e$ and $f$ cross at least once. Eggleton~\cite{E86} uses ``edge crossing number'' to denote what we would call the simple degenerate local crossing number (see entry for local crossing number).
\complexity Open. Bannister, Eppstein, and Simons~\cite{BES13} show that the $1$-page and $2$-page variants are fixed-parameter tractable for $k$-almost trees (with $k$ being the parameter).
\relations $\ecr(G) \leq \recr(G)$\index{rectilinear edge crossing number} (by definition). $\ecr(G) \leq \cro(G)$, $\recr(G) \leq \rcr(G)$\index{rectilinear crossing number} and inequality can be strict (since $\ecr(G)$ and $\recr(G)$ are bounded by $|E|$).
\values $\maxrecr(K_n)$\index{maximum rectilinear edge crossing number} is known for all $n$~\cite{I08}.
\end{cn}

\entry{Faithful crossing number} See string crossing number.

\begin{cn}{Fixed linear crossing number}\mindex{fixed linear crossing number}
\defn The {\em fixed linear crossing number}, $\bkcr_k(G,\pi)$ of an ordered graph $(G,\pi)$ in a book with $k$ pages, is the smallest number of crossings in a drawing of $G$ in a book with $k$ pages so that all vertices lie on the spine of the book in the order prescribed by $\pi$ and each edge lies on a single page. If $\pi$ orders only a subset $A \subseteq V(G)$ of the vertices (the {\em anchors}) and the remaining vertices are not required to lie on the spine, we obtain the {\em anchored crossing number}\mindex{anchored crossing number}, $\bkcr_k(G,A,\pi)$.
\reference Masuda, Nakajima, Kashiwabara, Fujisawa~\cite{MNKF90} for $\bkcr_2(G,\pi)$. Cabello, Mohar~\cite{CM10} for $\bkcr_1(G,A,\pi)$.
\comments A close variant of the book crossing number\index{book crossing number}, it could also be called the fixed book crossing number\index{fixed book crossing number}; $\bkcr_1(G,\pi)$ has been called the {\em chordal crossing number}\index{chordal crossing number}~\cite{Z12}. Cabello and Mohar defined the special case of anchors lying on the boundary of a disk and the drawing lying within the disk, which is equivalent to $\bkcr_1(G,A,\pi)$.
\complexity Testing $\bkcr_k(G,\pi)$ is obviously in polynomial time for $k=1$ and \NP-complete for $k=2$~\cite{MNKF90} (even if each connected component is a single edge). This implies that the problem is \NP-complete for $k \geq 2$.\footnote{To add a page, surround each vertex by many nested edges. Then all these added edges have to lie in a separate page. This simple construction fails, of course, if the ordering cannot be specified.} As in the case of the book crossing number, the embedding problem is of special interest here. The problem of deciding whether $\bkcr_k(G,\pi) = 0$ on input $(G,\pi)$ and $k$ was shown \NP-complete by Garey, Johnson, Miller, and Papadimitriou~\cite{GJMP80}, but they left open the question of what happens for fixed $k$. This was settled by Unger who showed that $\bkcr_3(G, \pi) = 0$ can be tested in time $O(n\log n)$~\cite{U92} while testing $\bkcr_k(G, \pi) = 0$ is \NP-complete for any fixed $k\geq 4$~\cite{U88}.\footnote{All the embedding results are expressed for colorings of circle graphs, but the reduction is easy: given a graph $G$ with an ordering $\pi$, add a Hamiltonian cycle to $G$ extending that ordering, yielding $G'$. Then every non-cycle edge is a chord of the graph, and the endpoints of two chords alternate along the cycle if and only if  the chords have to go into different pages in a book embedding of $G$. Let $G''$ be the circle (chord intersection) graph of $G$. Then $k$-colorability of $G''$ is equivalent to $G$ being embeddable in $k$ pages with the given ordering. This is sufficient to show that testing $\bkcr_k(G, \pi)$ is \NP-complete for $k \geq 4$: Given a circle graph one can use Spinrad's algorithm to construct a circle model $G'$ for it, from which one can get a graph $G$ with an ordering of vertices $\pi$, so that the circle graph is $k$-colorable, if and only if $(G,\pi)$ has a $k$-page embedding respecting $\pi$, that is $\bkcr_k(G,\pi) = 0$.} Cimikowski~\cite{C06} has studied various heuristics for computing $\bkcr_2(G,\pi)$.
For the anchored version, Cabello and Mohar~\cite{CM10} showed that $\bkcr_1(G,A,\pi)$ is \NP-complete even if $G$ consists of two vertex disjoint planar graphs.\footnote{This was the main intermediate step in their proof that computing the crossing number of an almost planar graph is \NP-complete.}
\relations $\mcro(G,\pi) \leq \bkcr_2(G,\pi)$\index{monotone crossing number} for ordered graphs $(G,\pi)$ (from definition).
\also Book crossing number.
\end{cn}

\entry{Fixed monotone crossing number} See monotone crossing numbers.

\entry{Fractional crossing number} See weighted crossing number.

\begin{cn}{Genus crossing number}\mindex{genus crossing number}
\defn The {\em genus crossing number} of a drawing $D$ of a graph $G$ is the number of points in which edges cross each other (that is, we count this point only once, not ${k \choose 2}$ times for $k$ edges passing through it); we do not allow edges to touch in the shared point, but we do allow self-crossings of an edge (so an edge can pass through the same crossing point multiple times at no additional cost). The genus crossing number of a graph $G$, $\gcr(G)$, is the smallest number of crossing points in a drawing of $G$.
\reference Mohar~\cite{M09}.
\comments Mohar proves that the genus crossing number equals the non-orientable genus of a graph. He conjectures that $\gcr(G) = \dcr(G)$~\cite{M09}.
\complexity \NP-complete~\cite{M09} (since Carsten Thomassen showed that determining the non-orientable genus of a graph is \NP-complete~\cite{MT01}).
\relations $\gcr(G) \leq \mcr(G)$\index{minor crossing number} since $\gcr$ is minor-monotone. There are graphs for which $\gcr(G) < \mcr(G)$~\cite{M09}. Also, $\gcr(G) \leq \dcr(G)$\index{degenerate crossing number} by definition.
\values Exact results for the non-orientable genus of $K_m$ and $K_{m,n}$ were given by Ringel, see~\cite{ESZ06} for a discussion.
\also Degenerate crossing number.
\end{cn}

\begin{cn}{Geodesic crossing number}\mindex{geodesic crossing number}
\defn The {\em geodesic crossing number}, $\rcr_{S}(G)$, on a metric surface $S$, is the smallest number of crossings in a drawing of $G$ on $S$ where each edge is represented by a geodesic (with respect to the metric) in $S$.\footnote{Intuitively, geodesics are locally shortest arcs. Note that a geodesic is not necessarily a shortest arc between two points on a surface, and it need not be unique, as the example of antipodal points on the sphere shows.} Special cases include the rectilinear crossing number\index{rectilinear crossing number}, where $S$ is the plane with the Euclidean metric (in which case we write $\rcr$), the {\em spherical (geodesic) crossing number\mindex{spherical crossing number}}~\cite{M65,L00,W06}, where $S$ is the unit ball $S^2$ in three-dimensional Euclidean space, and the {\em toroidal geodesic crossing number}\mindex{toroidal geodesic crossing number}, where $S$ is a (geometric) torus in three-dimensional Euclidean space.
\reference Guy, Jenkyns, Schaer~\cite{GJS68}, also Harary, Hill~\cite{HH63}.
\comments The spherical geodesic crossing number of complete graphs is discussed by Harary and Hill~\cite{HH63}. Moon~\cite{M65} studies the number of crossings in a random geodesic drawing of $K_n$ on the sphere (vertices are picked at random, edges are shortest arcs). Both spherical and toroidal geodesic crossing numbers are introduced and studied explicitly in~\cite{GJS68}. It is not clear from the paper whether the authors believe that the toroidal geodesic crossing number is independent of the actual geometric shape of the torus; they concentrate on a single model (the unit square with opposite sides identified). They explicitly equate the rectilinear crossing number with the geodesic crossing number, even though Harary and Hill~\cite{HH63} had earlier realized that $K_8$ has a geodesic drawing on the sphere with at most $18$ crossings, whereas $\cro(K_8) = 19$ was unproven, but expected to be true at the time. Guy~\cite{G71b,G72} later realized that the spherical crossing number of $K_n$ is at most $Z(n) = X(n)X(n-2)/4$, where $X(n) = \lfloor n/2 \rfloor \lfloor (n-1)/2\rfloor$; this again shows that the spherical crossing number of $K_8$ is at most $18$. Since he could also show that $\rcr(K_8) = 19$ (also Barton~\cite{B70} and Singer~\cite{S71}), this separates rectilinear and spherical crossing number. It is not clear whether all papers discussing geodesic crossing numbers distinguish between shortest arcs and geodesics (exceptions are~\cite{M65,W06} which explicitly define the geodesic crossing number in terms of shortest arcs rather than geodesics).
\complexity Open, but likely to be \NPR-hard (and in \NPR\ assuming the metric is natural), see~\cite{S10b} for \NPR.
\relations $\rcr_{S^2}(G) \leq \rcr(G)$\index{rectilinear crossing number} (a sufficiently small drawing of $G$ will realize this).
$\rcr_{S^2}(K_n) \leq Z(n)$, where $Z(n) = X(n)X(n-2)/4$, with $X(n) = \lfloor n/2 \rfloor \lfloor (n-1)/2\rfloor$, is Zarankiewicz's function, the conjectured upper bound on $\cro(K_n)$~\cite{G72,RT97,W06}.\footnote{This result is claimed by Guy in~\cite{G72} without any details. One can use the cylindrical drawings of Richter and Thomassen~\cite{RT97} to see that the inequality is true. Wagner~\cite{W06} obtains this result as an application of Gale duality.}
\openq Is there a Fary theorem for metric surfaces? That is, is it true that $\cro_S(G) = 0$ implies that $\rcr_S(G) = 0$\index{rectilinear crossing number} for a surface $S$ equipped with a ``natural'' metric?\footnote{Thomassen~\cite{T11} points out that it is likely that one can construct metrics for which this fails, but what about standard metrics?} Does it matter whether the geodesic crossing number is defined in terms of geodesics or shortest arcs? Shortest arcs can cross more than once (without overlapping) in some surfaces; are there examples of graphs for which every optimal geodesic (or shortest arc) drawing requires some edges to cross more than once?\footnote{\label{foot:pcrvscr} The answer is yes for pseudosurfaces: take a sphere and two tori and attach each torus to the sphere at a single point (using two distinct points). Take two copies of a graph whose planar crossing number is large but which can be embedded on the torus. Connect the two graphs by two edges whose endpoints are adjacent in the toroidal graphs. Then the graph has a geodesic drawing in which only the two edges cross, namely in the points of attachment. In particular, the geodesic pair crossing number\index{geodesic pair crossing number} differs from the geodesic crossing number for this pseudosurface.}
\also Rectilinear crossing number.
\end{cn}

\begin{cn}{Grid crossing number}\mindex{grid crossing number}
\defn A {\em $d$-dimensional grid drawing} of a graph $G$ is a geometric (straight-line) embedding of $G$ into $\NN^d$, that is, vertices are assigned to points in $\NN^d$, edges are straight-line segments between their endpoints, and we require that no vertex lies on an edge, unless it is an endpoint of that edge. The {\em volume} of a $d$-dimensional grid drawing of $G$ is the volume of a smallest axis-parallel box containing all points of the grid drawing. The {\em $d$-dimensional volume $N$ grid crossing number} of $G$, $\gridcr(G,N,d)$ is the smallest number of crossings in a $d$-dimensional grid drawing of $G$ of volume at most $N$.
\reference Based on Dujmovi\'{c}, Morin, Sheffer~\cite{DMS14}, Swamy~\cite[Q5]{S09} for name.
\comments Dujmovi\'{c}, Morin, Sheffer~\cite{DMS14} introduce the crossing number of a grid graph (what we called a grid drawing), which they write $\cro(G)$, $G$ being a grid graph/drawing, and then study the crossing number of that, in particular, the parameter $\cro_d(N,m) = \min\{\cro(G): G$ is a $d$-dimensional grid drawing of a graph with $m$ edges and volume at most $N\}$, which is quite natural, since their main goal is a crossing lemma result for grid graphs. They point to several previous papers that have studied grid embeddings, that is, grid drawings without crossings (also called non-crossing grid graphs in the literature), but theirs seems to be the first paper to study the crossing number notion. The $2$-dimensional grid crossing number is a refinement of the rectilinear crossing number\index{rectilinear crossing number}. It is well-known that $\rcr(G)$ can be realized on a grid of double exponential size and that grids of that size are necessary for some graphs (Bienstock~\cite{B91}). It is in this context that Swamy~\cite{S09} coined the term grid crossing number.
\complexity \NP-complete for $d = 2$.\footnote{Bienstock~\cite{B91} showed that for every $G$ there is a $G'$ with $\cro(G) = \rcr(G')$, where $G'$ is obtained from $G$ by subdividing each edge at most $cn^2$ times (for some fixed $c>0$). We claim that $\cro(G) = \gridcr(G',cn^2,2)$ which implies that computing $\gridcr(G,N,2)$ is \NP-hard. To see that
$\rcr(G') = \gridcr(G',cn^2,2)$, take an $\rcr$-optimal drawing of $G'$. Replace each crossing with a (very small) $C_4$ close to that crossing, so that the corners of $C_4$ become the endpoints of the four half-edges meeting at the crossing. Triangulate the drawing, keeping the $C_4$-faces empty; the resulting graph is $3$-connected, so by a result from~\cite{CK97}, it has an embedding on the $(n-2) \times (n-2)$ grid in which all faces are convex. In particular, we can replace each $C_4$ by two diagonal edges, and remove all triangulation edges to obtain a grid drawing of $G'$.}
\relations $\rcr(G) \leq \gridcr(G,N,2)$ (by definition), and $\rcr(G) = \gridcr(G,N,2)$ for $N = 2^{2^{cn}}$ for some $c>0$\footnote{Folklore result; true, because $\rcr(G) \leq k$ can be expressed in the existential theory of the reals, see~\cite{S10b}, for example.} and there are graphs for which $\rcr(G) < \gridcr(G,N,2)$ if $N = 2^{2^{dn}}$ for some $0 < d$~\cite{B91}. $\gridcr(G,N,2) = \Theta(m^3/N^2)$ for $m \geq 4N$ (follows from~\cite{ACNS82} as observed in~\cite{DMS14}),
$\gridcr(G,N,3) = \Omega(m^2/N \log\log (m/N))$ for $m \geq 2(2^d-1)N$,
$\gridcr(G,N,3) = \Omega(m^2/N \log (m/N))$, and $\gridcr(G,N,d) \Omega(m^2/N)$~\cite{DMS14}.
\values $\cro(G,(n-2)^2,2) = 0$ for planar graphs $G$~\cite{S90a}. For complete graphs, it is known that $\cro(K_n, 4n^3, 3) = 0$, and $\cro(K_n, o(n^3),3) > 0$~\cite{CELR97}.
\openq What is the complexity of computing $\cro(G,N,d)$ for dimensions $d>2$?
\also Space crossing number, rectilinear crossing number.
\end{cn}

\begin{cn}{Independent algebraic crossing number}\mindex{independent algebraic crossing number}
\defn The {\em independent algebraic crossing number} of $G$, $\iacr(G)$, is defined like $\acr(G)$ except that we do not count $\acr(e,f)$ for adjacent edges $e$ and $f$.
\reference Tutte~\cite{T70}.
\comments Tutte's paper ``Toward a Theory of Crossing Numbers'' is often cited claiming it (implicitly) contains all kinds of crossing number definitions. A look at the text shows that Tutte defines two crossing numbers: the standard crossing number\index{crossing number} (which he calls $c(G)$) and what we now call the independent algebraic crossing number\index{independent algebraic crossing number}; his crossing chains count crossings algebraically, that is, over $\ZN$, not modulo $2$ as the odd crossing numbers do; moreover, he sets the coefficients of pairs of adjacent edges to $0$ so they don't count. The crossing number he defines based on that, $s(G)$, is $\iacr(G)$. Tutte writes: ``It is clear that $c(G) \geq s(G)$. Does equality always hold?'' This question was answered in the negative by T\'{o}th~\cite{T08} who constructed a graph $G$ with $\iacr(G)  = \acr(G) < \cro(G)$\index{algebraic crossing number}.
\complexity In \NP\ (similar to algebraic crossing number). It is possible that \NP-hardness can be achieved along similar lines as in~\cite{PSS09d}.
\relations $\iacr(G) \leq \acr(G)$ and $\iocr(G) \leq \iacr(G)$\index{independent odd crossing number} (by definition). It follows from results in~\cite{PSS08} that there are graphs $G$ for which $\iocr(G) < \iacr(G)$.
\also Algebraic crossing number, independent odd crossing number.
\end{cn}

\begin{cn}{Independent crossing number}\mindex{independent crossing number}
\defn The {\em independent crossing number} of $G$, $\cro_-(G)$, is the smallest number of crossings between pairs of independent edges in any drawing of $G$.
\reference Pach, T\'{o}th~\cite{PT00b}.
\comments The first explicit definition of the independent crossing number seems to be in Pach, T\'{o}th~\cite{PT00b}. Not counting crossings between adjacent edges is implicit in many early papers, and, for straight-line or geodesic drawings, entirely justified~\cite{M65}.
\complexity \NP-complete.
\relations $\pcr_- (G) \leq \cro_-(G) \leq \cro(G)$\index{independent pair crossing number} (from definition).
\openq It is not known whether $\cro_-(G) < \cro(G)$\index{crossing number} is possible. This would follow from a separation of the corresponding monotone crossing numbers~\cite{FPSS12b}.
\end{cn}

\begin{cn}{Independent odd crossing number}\mindex{independent odd crossing number}
\defn The {\em independent odd crossing number} of $G$, $\iocr(G)$, is the smallest number of independent pairs of edges crossing an odd number of times in any drawing of $G$.
\reference Sz{\'e}kely~\cite{S04}.
\comments This variant seems to have been introduced and named by Sz{\'e}kely. He attributes it to Tutte~\cite{T70}, but Tutte really defined the independent {\em algebraic} crossing number\index{independent algebraic crossing number}.\footnote{Parity is only mentioned in one short passage in Tutte's paper~\cite{T70}, and that occurs when he observes that for two edges $e$ and $f$, $\acr(e,f) \equiv \cro(e,f) \bmod{2}$.}
\complexity \NP-complete~\cite{PSS09d} even if restricted to cubic graphs.
\relations $\iocr(G) \leq \ocr(G)$\index{odd crossing number} for all graphs $G$ (by definition). $\iocr(G) = \ocr(G) = \cro(G)$\index{crossing number} for $\iocr(G) \leq 2$~\cite{PSS10}, generalizing the Hanani-Tutte theorem. There are graphs $G$ for which $\iocr(G) < \ocr(G)$~\cite{FPSS12b}. $\cro(G) \leq {2\iocr(G) \choose 2}$~\cite{PSS10}; this implies that $\ocr$, $\acr$\index{algebraic crossing number}, $\pcr$\index{pair crossing number}, $\cro$ and all their $+$ and $-$ variants are within a square of each other. There is a crossing lemma: $\iocr(G) \geq 1/64 m^3/n^2$.\footnote{For a proof, see the section on crossing lemma variants in Section~\ref{sec:WCN}.} There are algebraic sufficiency criteria for $\iocr(G) = \cro(G)$~\cite{S08}. For surfaces other than the sphere, the only known result is that $\iocr_{N_1}(G) = 0$\index{independent odd projective plane crossing number} implies $\cro_{N_1}(G) = 0$~\cite{PSS09c}. A smallest counterexample to $\iocr_{\Sigma}(G) = 0$ implying $\cro_{\Sigma}(G) = 0$ must be $2$-connected~\cite{SS13}.
\also Odd crossing number, independent algebraic crossing number (under algebraic crossing number), monotone crossing number (for monotone version).
\end{cn}

\entry{Independent pair crossing number} See pair crossing number.

\entry{Independent string crossing number} See string crossing number.

\entry{Inner crossing number} See bipartite crossing number.

\begin{cn}{Joint crossing numbers}\mindex{joint crossing numbers}
\defn Suppose $G_1$ and $G_2$ are graphs embedded in the same surface $\Sigma$; a {\em joint embedding} of $G_1$ and $G_2$ is a simultaneous embedding of homeomorphic copies of $G_1$ and $G_2$ in which the only shared points between $G_1$ and $G_2$ are (transversal) crossings of an edge of $G_1$ with an edge of $G_2$; if we restrict the homeomorphisms to be orientation-preserving, we speak of a {\em joint orientation-preserving embedding}. If we restrict the homeomorphisms so that all vertices of $G_1$ lie in a face of $G_2$ and vice versa, we call the joint embedding {\em single-faced}. The {\em (joint) crossing number} of $G_1$ and $G_2$, $\cro(G_1,G_2)$, is the smallest number of crossings in any joint embedding of $G_1$ and $G_2$ in $\Sigma$, the {\em oriented crossing number}\mindex{oriented crossing number}, $\orcr(G_1,G_2)$ of $G_1$ and $G_2$, is the smallest number of crossings in any joint orientation-preserving embedding of $G_1$ and $G_2$. The {\em single-faced crossing number}\mindex{single-faced crossing number}, $\sfcr(G_1,G_2)$, is the smallest number of crossings in any single-faced joint embedding of $G_1$ and $G_2$. Similarly, $\sfocr(G_1,G_2)$, is the {\em single-faced oriented crossing number}\mindex{single-faced oriented crossing number}. We can relax the notion of joint embedding to a {\em diagonal embedding} by allowing vertices of $G_1$ to coincide with vertices of $G_2$ and edges of $G_1$ to coincide with edges of $G_2$. The smallest number of crossings in a diagonal embedding is the {\em diagonal crossing number}\mindex{diagonal crossing number}, $\diagcr(G_1,G_2)$. If we want to emphasize the underlying surface, we write $\cro(G_1,G_2;\Sigma)$, for example. If instead of embedded graphs $G_1$, $G_2$ we have abstract topological graphs that are embeddable in $\Sigma$, we can still define the {\em crossing number} and the {\em diagonal crossing number} of $G_1$ and $G_2$ by additionally minimizing over all embeddings of $G_1$ and $G_2$. Richter and Salazar~\cite{RS05} suggest the notation $\cro(\phi_1(G_1), \phi_2(G_2))$ for the embedded graph variant ($\phi_i(G_i)$ is a class of homeomorphic embeddings of $G_i$); we will rely on context.
\reference Negami~\cite{N98,N01}. Also, Archdeacon, Bonnington~\cite{AB01}, Richter, Salazar~\cite{RS05}.
\comments Joint crossing numbers, that is crossings numbers of pairs of (embedded) graphs were first introduced by Negami~\cite{N98,N01}. Archdeacon and Bonnington~\cite{AB01} restrict joint embeddings to orientation-preserving homeomorphisms, so their joint crossing number is what Negami called the oriented crossing number. Negami simply uses crossing number for the joint crossing number. We will not use the term joint crossing number to refer to a particular variant. Richter and Salazar~\cite{RS05} explicitly define the single-faced crossing number\index{single-faced crossing number} which is implicit in Archdeacon, Bonnington~\cite{AB01}.
As examples for values of joint crossing numbers, Negami gives $\cro(K_5, K_{3,3}; S_1) = 2$ and $\diagcr(K_5, K_{3,3};S_1) = 0$\index{diagonal crossing number}. Since $G_1$ and $G_2$ are both required to be embeddable on $\Sigma$, the crossing number of pairs is always $0$ for the plane.
\complexity Open.
\openq Negami~\cite{N01} conjectures that $ \cro(G_1,G_2) \leq c |E(G_1)| \cdot |E(G_2)|$ for some constant $c$ independent of $\Sigma$; Archdeacon and Bonnington~\cite{AB01} believe this conjecture to be false. They conjectured that $\orcr(G_1,G_2) \leq c_{\Sigma} \cdot \sfocr(G_1,G_2)$\index{single-faced crossing number}\index{oriented crossing number} for embedded graphs $G_1$ and $G_2$ which was shown to be false by Richter and Salazar~\cite{RS05} (who suggest a revised conjecture).
\relations $\diagcr(G_1,G_2) \leq \cro(G_1,G_2)$\index{diagonal crossing number} (from definition). If $\gamma(\Sigma)$ is the (orientable or non-orientable) genus of $\Sigma$, then $\orcr(G_1,G_2; \Sigma) \leq 4\gamma(\Sigma) |E(G_1)| \cdot |E(G_2)|$\index{oriented crossing number}, and $\orcr(G_1,G_2; S_1) \leq 2/3 |E(G_1)| \cdot |E(G_2)|$~\cite{N01,AB01}.
\values $\cro(G_1,G_2; S_n) = 2n$ if both $G_1$ and $G_2$ are $2$-cell embedded on $S_n$ so that each embedding has a single face~\cite{WRX11}.
\also Simultaneous crossing number. Red/blue crossing number.
\end{cn}

\begin{cn}{$k$-layer crossing number}\mindex{k layer crossing number@$k$-layer crossing number}
\defn A {\em leveling} of a graph $G = (V,E)$ is a mapping from $V$ to $\{1,\ldots,k\}$, assigning each vertex a level. The leveling is {\em proper} if all edges of $G$ are between vertices at adjacent levels. A {\em layered} drawing of a properly leveled (layered) graph is a drawing in which the vertices are placed on $k$ parallel lines, with vertices in layer $i$ assigned to the $i$th line, and edges are drawn as straight-line segments. The {\em $k$-layer crossing number} of a layered graph is the smallest number of crossings in a $k$-layer drawing of the graph.
\reference Warfield~\cite{W77}, Sugiyama, Tagawa, Toda~\cite{STT81}, Shahrokhi, Vr{\v{t}}o~\cite{SV99}.
\comments Shahrokhi and Vr{\v{t}}o~\cite{SV99} introduced (and named) the $3$-layer crossing number, but as a crossing minimization problem the $k$-layer crossing number is already present in papers by Warfield~\cite{W77} and Sugiyama, Tagawa, and Toda~\cite{STT81}; these earlier papers write $K(M)$ for the layered crossing number of a leveled graph represented by a matrix $M$. The $2$-layer crossing number is just the bipartite crossing number\index{bipartite crossing number}. Layered crossing numbers are similar to leveled crossing numbers\index{leveled crossing number}, except that for the layered crossing numbers edges have to be realized as straight-line segments (rather than just being monotone); if the leveling is proper, the leveled and layered crossing numbers coincide. Leveling a graph imposes a linear structure on the graph. One could also imagine allowing other structures, for example trees~\cite{P12}, or cycles as in the cyclic level crossing number. Wotzlaw, Speckenmeyer and Porschen~\cite{WSP12} consider the case in which the ordering of the vertices in each layer is restricted by a tree (a generalization of the tanglegram\index{tanglegram} problem, also see the comment in the entry on the bipartite crossing number).
\complexity \NP-complete~\cite{GJ83}.\footnote{The reduction by Garey and Johnson~\cite{GJ83} is to bipartite multigraphs. The middle layer can be used to replace multiple edges by parallel paths.} Can be approximated to within a factor of $O(\log n)$ in polynomial time~\cite{SV99}. The embeddability problem can be decided in polynomial time and this remains true if the ordering of vertices in each layer is constrained by trees~\cite{WSP12}.
\relations The $k$-layer crossing number of $G$ is at most $\rcr(G)$\index{rectilinear crossing number} and it can be strictly less than $\rcr(G)$. The leveled crossing number is a lower bound on the $k$-layer crossing number.
\openq If a graph has leveled crossing number zero, that is, if it has a monotone leveled embedding, it has an embedding in which all edges are straight-line segments~\cite{EFL96,PT04}, though the area of the graph may increase exponentially~\cite{LE03}. Are there leveled graphs for which the $k$-layer crossing number is strictly larger than the leveled crossing number?
\also Bipartite crossing number, leveled crossing number (under monotone crossing number), cyclic level crossing number.
\end{cn}

\entry{$k$-page crossing number} See book crossing number.

\begin{cn}{$k$-planar crossing number}\mindex{k planar crossing number@$k$-planar crossing number}
\defn The {\em $k$-planar crossing number}, $\cro_k(G)$, of $G = (V,E)$ is the minimum of $\sum_{i=1}^k \cro(G_i)$, where the minimum is taken over all $G_i = (V,E_i)$ with $\bigcup_{i=1}^k E_i = E$. The special case $\cro_2$ is also known as the {\em biplanar crossing number}\mindex{biplanar crossing number}. If we restrict the drawings to be rectilinear, we get $\rcr_k$, the {\em rectilinear $k$-planar crossing number}\mindex{rectilinear k planar crossing number@rectilinear $k$-planar crossing number}. The {\em thickness}, $\Theta(G)$, is the smallest $k$ such that $\cro_k(G) = 0$; similarly, the {\em geometric thickness}, $\overline{\Theta}(G)$, is the smallest $k$ such that $\rcr_k(G) = 0$.
\reference Owens~\cite{O71}, Shahrokhi, S{\'y}kora, Sz{\'e}kely, Vr\v{t}o~\cite{SSSV07}.
\comments Owens~\cite{O71} introduced the $k$-planar crossing number for arbitrary $k$, but focussed on the biplanar case, Shahrokhi, S{\'y}kora, Sz{\'e}kely, Vr\v{t}o introduced the rectilinear version. The $k$-planar crossing numbers have also been called the {\em multiplanar crossing numbers}\index{multiplanar crossing numbers}~\cite{dKPS12b}.
\complexity The $k$-planar crossing number is \NP-complete, since the embedding problem $\cro_k(G) = 0$ is equivalent to the thickness of $G$ being at most $k$ and even for $k=2$ this problem is \NP-complete~\cite{M83}. The rectilinear $k$-planar crossing number is \NPR-complete, since it coincides with $\rcr$ for $k=1$, but the case $k \geq 2$ is open, though likely to be \NPR-complete as well.
\relations $\cro_1 = \cro$\index{crossing number} and $\rcr_1 = \rcr$\index{rectilinear crossing number} (by definition). $\cro_2(G) \leq (3/8) \cro(G)$~\cite{CSSV08}. $\cro_k(G) \leq \bkcr_{2k}(G)$\index{book crossing number}.\footnote{Observed by Winterbach~\cite{W05}, follows from $\cro(G) \leq \mcro(G) \leq \bkcr_2(G)$\index{monotone crossing number}. Winterbach~\cite[Question 8.2.5]{W05} asks whether there are graphs $G$ for which $\cro_k(G) < \bkcr_{2k}(G)$. DeKlerk, Pasechnik, and Salazar give a positive answer in~\cite{dKPS12b} for $G = K_{2k+1,k^2+2000k^{7/4}}$ by showing that $\bkcr_{2k}(G) > 0$, while $\cro_k(G) = 0$ by a result of Beineke's.} There is a crossing lemma, $\cro_k(G) \geq 1/64 m^3/(n^2 k^2)$, where $n = |V(G)|$ and $m = |E(G)|$~\cite{SSSV07}. On the other hand, $\cro_k(G) \leq 1/(12k^2) (1-1/(4k))m^2 + O(m^2/(kn))$~\cite{SSSV07}.
\values See~\cite{CSSV06} for a comprehensive survey of biplanar crossing numbers\index{biplanar crossing number} of complete graphs, complete bipartite graphs and some other graph families, also~\cite{R07b,L09}. For values of $k$-planar crossing numbers of complete and complete bipartite graphs, see~\cite{SSSV07}.
\end{cn}

\entry{Klein bottle crossing number} See crossing number.

\entry{Leveled crossing number} See monotone crossing numbers.

\entry{Linear crossing number} See book crossing number. Very rarely used as synonym for rectilinear crossing number.

\entry{Local convex crossing number} See convex crossing number.

\begin{cn}{Local crossing number}\mindex{local crossing number}
\defn The {\em local crossing number} of a drawing $D$ of a graph $G$, $\lcr(D)$, is the largest number of crossings on any edge of $G$. The {\em local crossing number} of $G$, $\lcr(G)$, is the minimum of $\lcr(D)$ over all drawings of $G$. Define the {\em simple local crossing number}\mindex{simple local crossing number} $\lcr^*(G)$ as the minimum of $\lcr(D)$ over all {\em intersection-simple}\index{intersection-simple} drawings $D$ of $G$ (every two edges intersect at most once). For the local crossing number on a surface $\Sigma$, we write $\lcr_{\Sigma}$. If we count multiple crossings only once, we get the (simple) degenerate local crossing number.\mindex{degenerate local crossing number}\mindex{simple degenerate local crossing number}
\reference Kainen~\cite{K73}. Also, Ringel~\cite{R65}, Guy, Jenkyns, Schaer~\cite{GJS68}. For the simple local crossing number, see Schumacher~\cite{S90} and Pach, T\'{o}th~\cite{PT97}. The simple degenerate local crossing number was introduced by Eggleton~\cite{E86}.
\comments The local crossing number is mentioned in passing by Guy, Jenkyns, and Schaer~\cite{GJS68} who attribute it to Ringel (unpublished). They define the {\em local toroidal crossing number}\mindex{local toroidal crossing number}, the local crossing number on a torus, $\lcr_{S_1}$. Kainen~\cite{K73} later credits Ringel~\cite{R65}. Ringel's paper shows that a graph with at most one crossing per edge can be $7$-colored, but he doesn't develop a separate notion of crossing number (or name it). Graphs that can be drawn with at most one crossing per edge were later called {\em $1$-embeddable} (Ringel~\cite{R81}), {\em $1$-planar\footnote{Not to be confused with the notion of $k$-planarity in the multi-planar crossing number.}\index{1-planar}} (Schumacher~\cite{S86}) and even {\em simple}, on occasion~\cite{BEJKMW06}; the drawn graph has been called {\em $1$-immersed}~\cite{KM08}. Kainen~\cite{K74} considered the local crossing number on arbitrary surfaces, he shows that $\Theta_{\Sigma}(G) \leq 1 + \lcr_{\Sigma}(G)$, with $\Theta_{\Sigma}(G)$ being the thickness of $G$ on surface $\Sigma$. Cimikowski~\cite{C92} in his definition of local crossing number restricts drawings to be $\cro$-minimal. It is easy to see that this leads to a different notion of local crossing number. Harary, Kainen, and Schwenk~\cite{HKS73} gave as an example $W_5 \times K_2$ which has crossing number $2$ and local crossing number $1$, but any drawing of $W_5 \times K_2$ realizing crossing number $2$ has local crossing number at least $2$. They conjecture that their example is the smallest possible.
Eggleton~\cite{E86} introduces a degenerate version of the local crossing number, that is, he counts multiple crossings as a single crossing (he also restricts drawings to be intersection-simple)\index{intersection-simple}; he calls this variant the ``edge crossing number''\index{edge crossing number}, not to be confused with the notion of edge crossing number we introduce. Eggleton shows that every outerplanar drawing in which each edge has at most one degenerate crossing is rectifiable (realizable by straight-line segments and maintaining topological equivalence). Thomassen~\cite{T88} calls $\lcr(D)$ the {\em cross-index}\index{cross index} of $D$ and studies conditions under which drawings $D$ with $\lcr(D) \leq 1$ are rectifiable (realizable by straight-line segments, maintaining topological equivalence); this suggests the notion of {\em geometric/straight-line $1$-planarity}~\cite{HELP12,S13,D13}, or, more generally, a {\em rectilinear local crossing number}\index{rectilinear local crossing number}, $\rlcr$. Schumacher~\cite{S90} uses the term {\em $n$-embeddable} for graphs $G$ with $\lcr(G) \leq n$, and claims that if we take a drawing $D$ of $G$ with $\lcr(D) \leq n$ and a minimal number of crossings, ``none of $G$'s edges is crossing itself; two different edges with one vertex in common do not cross either, and two different edges without a vertex in common cross once at the most.'' The claim about self-crossings is obviously true, but the remaining two claims are false. See the graph in the margin
\marginpar{
\begin{pspicture}(0,0)(60,40)
\cnode*(0,0){1pt}{v1}
\cnode*(30,0){1pt}{v2}
\cnode*(60,0){1pt}{v3}
\cnode*(60,15){1pt}{v4a}
\cnode*(60,20){1pt}{v4b}
\cnode*(60,25){1pt}{v4c}
\cnode*(60,40){1pt}{v5}
\cnode*(39,40){1pt}{v6a}
\cnode*(42,40){1pt}{v6b}
\cnode*(45,40){1pt}{v6c}
\cnode*(48,40){1pt}{v6d}
\cnode*(51,40){1pt}{v6e}
\cnode*(15,40){1pt}{v7}
\cnode*(0,40){1pt}{v8}
\cnode*(0,29){1pt}{v9a}
\cnode*(0,26){1pt}{v9b}
\cnode*(0,23){1pt}{v9c}
\cnode*(0,20){1pt}{v9d}
\cnode*(0,17){1pt}{v9e}
\cnode*(0,14){1pt}{v9f}
\cnode*(0,11){1pt}{v9g}
\cnode*(30,20){1pt}{v0}

\ncline{v1}{v3}
\ncline{v3}{v5}
\ncline{v5}{v8}
\ncline{v8}{v1}

\ncline[linewidth=0.3]{v9d}{v0}
\ncline[linewidth=0.3]{v0}{v4a}
\ncline[linewidth=0.3]{v0}{v4b}
\ncline[linewidth=0.3]{v0}{v4c}

\nccurve[linewidth=0.3,angleA=120, angleB=-135,ncurv = 1.5]{v2}{v6c}
\nccurve[linewidth=0.3,angleA=60, angleB=-45, ncurv = 1.5]{v2}{v7}

\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9a}{v9g}
\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9b}{v9f}
\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9c}{v9e}

\nccurve[linewidth=0.3,angleA=-90, angleB=-90]{v6a}{v6e}
\nccurve[linewidth=0.3,angleA=-90, angleB=-90]{v6b}{v6d}

\end{pspicture}
}
for an example showing that adjacent edges can be forced to cross.\footnote{\label{foot:localdiff} This was also observed, without detailed proof, in~\cite[Figure~1]{PRTT06}. Some explanation of our example: consider a drawing of the graph with $\lcr(D) \leq 4$ in which the outer face is empty, in particular, the edges of the outer cycle are free of crossings. Then it is easy to argue that the two adjacent top/bottom edges have to cross in $D$. Here is how we enforce that the outer face is empty: add a new vertex and connect it to all vertices on the outer cycle. The vertices of this newly added star and the outer cycle form the {\em outer frame}. For each edge $uv$ in the outer frame, add $4|V(G)|+1 = 89$ parallel paths $P_3$ between $u$ and $v$; let the new graph be $G'$ and fix a drawing $D'$ with $\lcr(D') \leq 4$ and minimizing $\cro(D')$. We can assume that no two adjacent edges cross in $D'$ (otherwise we're done). Let $uv$ be an edge of the outer frame, and $xy$ be another edge. Then $uv$ and $xy$ cannot cross oddly: pick a cycle $C$ containing $xy$, but not $uv$ (if $xy$ also belongs to the outer frame, then the cycle can be completed with a $P_3$). The cycle has length at most $|V(G)| = 22$. Each of the $89$ cycles of the form $uv$ + $P_3$ crosses $C$ evenly, so if $uv$ crosses $xy$ oddly, then each of the $P_3$ must cross $C$ oddly, so some edge in $C$ has at least $89/22>4$ crossings, contradicting $\lcr(D') \leq 4$. So $uv$ crosses every edge evenly, so it crosses either one, or two edges. One can reduce the number of crossings in all cases, so $uv$ and thus all edges of the outer frame are free of crossings.}
A slight modification of this example shows that two edges can be forced to cross an arbitrary number of times in an $\lcr$-optimal drawing.
One could ask for an upper bound on the minimum number of crossings in a drawing $D$ of a graph with $\lcr(D) \leq n$. For $n=1$ this yields the
simple crossing number\index{simple crossing number}.
Pach and T\'{o}th~\cite{PT97} study the parameter we called the simple local crossing number without naming it.
Bodlaender and Grigoriev~\cite{BG07} rediscovered the local crossing number, calling it {\em crossing parameter}\index{crossing parameter}. In a later paper, Grigoriev, Koutsonas, and Thilikios~\cite{GKT13} use the term {\em $\xi$-nearly planar} for graphs with local crossing number at most $\xi$, and give an equivalent structural characterization of these graphs. For a convex (our outerplanar) version see the local convex crossing number\index{local convex crossing number} (under convex crossing number). Feng, Ye, and Xu~\cite{FYX12} suggest studying the minimal number of crossings along longest paths in a network (to model optical router networks); this has a similar flavor to the local crossing number, but is not strictly speaking a crossing number in our sense. With a similar motivation, Stallman and Gupta~\cite{SG10,S12} consider heuristics for the local crossing number of layered graphs, which they call the {\em bottleneck crossing number}\index{bottleneck crossing number}; to be precise, they really define what amounts to the local pair crossing number\index{local pair crossing number} in which we minimize the largest number of edges crossing each edge (not the actual crossings).\footnote{The local pair crossing number remains uninvestigated, but it would differ from the local crossing number, using examples similar to the ones presented above to separate local and simple local crossing numbers. The distinction was probably not intended by the authors of~\cite{SG10,S12}, since they also define the crossing number as $\pcr$. For layered drawings there is no difference between counting all local crossings or only counting local pair crossings.}
\complexity Deciding whether $\lcr(G) \leq 1$ is \NP-complete~\cite{BG07,KM08,CM13}, and there are results on its parameterized complexity~\cite{BCE13}. Known results imply that testing $\rlcr \leq 1$ is \NP-complete~\cite{S13}.
\relations $\lcr(G) \leq \lcr^*(G) \leq \cro(G)$\index{crossing number} by definition, and $\lcr(G) = \lcr^*(G)$ for $\lcr(G) \leq 3$,\footnote{\label{foot:localeq}For $\lcr(G) = 1$ this was observed by Ringel~\cite{R65}, for $\lcr(G) \leq 3$, see~\cite[Lemma 1.1]{PRTT06}.} and there are graphs $G$ with $4 = \lcr(G) < \lcr^*(G)$ (Footnote~\ref{foot:localdiff}). For every surface $\Sigma$ and every $k$ there is a graph so that $\lcr_{\Sigma}(G) = 1$ and $\cro_{\Sigma}(G) \geq k$~\cite{HKS73}. There is a graph $G$ with $\cro(G) = 2$ for which any drawing $D$ with $\lcr(D) \leq 1$ fulfills $\cro(D) \geq 3$~\cite{HKS73,BEJKMW06}. Let $m = |E(G)|$ and $n = |V(G)|$. Schumacher~\cite{S84,S90} showed that $m \leq (\lcr^*_S(G) + 3)(n - \chi)$, where $\chi$ is the Euler characteristic of the surface $S$ as long as $\lcr^*_S(G) \leq 2$, and that these bounds are tight.\footnote{The special case, $m \leq 4n-8$ for graphs with $\lcr^*(G) \leq 1$ on the sphere seems to go back to~\cite{BSW83}.}
Pach and T\'{o}th showed that $m \leq (\lcr^*(G) + 3)(n - 2)$ as long as $\lcr^*(G) \leq 4$, and that these bounds are tight for $\lcr^*(G) \leq 2$~\cite{PT97}. As it turns out, this is where the obvious pattern stops: $m \leq 5.5(n-2)$ for $\lcr^*(G) \leq 3$~\cite{PRTT06}, and
$m \leq 6(n-2)$ for $\lcr^*(G) \leq 4$~\cite{A13b} and both results are tight up to additive constants.\footnote{Ackerman~\cite{A13b} uses his result to derive an improved constant for the crossing lemma for $\cro$, following the same approach as~\cite{PRTT06}.} For unbounded $\lcr^*(G)$, the best current result is $m \leq 3.81\lcr^*(G)n$~\cite{A13b}, improving an earlier bound by~\cite{PT97}. For the rectilinear local crossing number Didimo~\cite{D13} showed that $\rlcr(G) \leq 1$ implies $m \leq 4n-9$ (and this bound is tight for infinitely many $n$).

\openq Is it true that $m \leq (\lcr^*_S(G) + 3)(n - \chi)$, where $\chi$ is the Euler characteristic of $S$, even just for $S$ being the sphere? We saw above that $\lcr(G) < \lcr^*(G)$ is possible; can $\lcr^*(G)$ be bounded in $\lcr(G)$?
\values $\lcr_{S_1}(K_n)$ is known for $n \leq 9$, and there are asymptotic results for $\lcr_{S_1}(K_n)$~\cite{GJS68}.
\also Local convex crossing number (under convex crossing number), Nodal crossing number, Simple crossing number.
\end{cn}

\entry{Local outerplanar crossing number} See convex crossing number.

\entry{Local toroidal crossing number} See local crossing number.

\entry{Major Crossing number} See minor crossing number.

\begin{cn}{Map crossing number}\mindex{map crossing number}
\defn A {\em map} is a graph $G=(V,E)$ and a surface $\Sigma$ with boundary $\partial \Sigma$ so that $V \subseteq \partial \Sigma$. In a drawing of $G$ each edge is realized by a properly embedded arc (a connected curve that intersects $\partial \Sigma$ in its endpoints only). The {\em crossing number} of the map is the smallest number of crossings in a drawing of the map. Similarly, one can define odd, algebraic and pair crossing number for maps. We can introduce special names based on the number of boundary components of $\Sigma$: {\em disk crossing number}\mindex{disk crossing number} (one hole), {\em annulus crossing number}\mindex{annulus crossing number} (two holes), {\em pair of pants crossing number}\mindex{pair of pants crossing number@pair-of-pants crossing number} (three holes), and so on.
\reference Pelsmajer, Schaefer, \v{S}tefankovi\v{c}~\cite{PSS08}.
\comments The map crossing numbers were introduced in~\cite{PSS08} to separate $\ocr$ from $\cro$. One can turn every boundary component into a single vertex with rotation\index{rotational crossing number}; as long as one is considering a crossing number variant in which adjacent crossings count the same as independent crossings, the crossing number notion does not change, so one can alternatively look at map crossing numbers as crossing numbers of graphs with rotation system; map crossing numbers can also be considered a special case of the constrained crossing number. If we allow vertices to arbitrarily move on their boundary component, the disk crossing number becomes the convex crossing number, and the annulus crossing number turns into the radial crossing number on two levels. (The general case does not seem to have been considered so far.)
\complexity The disk crossing number\index{disk crossing number} can be computed in time $\Theta(m \log m)$, where $m = |E|$; the annulus (algebraic) crossing number\index{annulus crossing number}\index{annulus algebraic crossing number} can be computed in polynomial time~\cite{PSS09d}.\footnote{Results in that paper are phrased for graphs with rotation systems.} The complexity of computing the pair-of-paints crossing number\index{pair of pants crossing number@pair-of-pants crossing number} is open. The general problem is \NP-complete, since computation of the crossing number of a graph with a given rotation is \NP-complete~\cite{PSS09d}.
\relations $\ocr(M) \leq \pcr(M) \leq \acr(M) = \cro(M)$ for any map $M$; there is a map $M$ for which $13 = \ocr(M) < \pcr(M) = 15$; if $\Sigma$ has $n$ boundary components, then $\cro(M) \leq \ocr(M) {n+4 \choose 4}/5$~\cite{PSS08}.
\also Radial crossing number (on two levels), crossing number (with rotation system), constrained crossing number, convex crossing number, cylindrical crossing number, joint crossing numbers, wire crossing number.
\end{cn}

\begin{cn}{Maximum crossing number}\mindex{maximum crossing number}
\defn The {\em maximum crossing number} of a graph $G$, $\maxcro(G)$, is the largest number of crossings in any drawing of $G$ in which every pair of edges has at most one point in common (a shared endpoint counts, touching points are forbidden).\footnote{In other words: an intersection-simple\index{intersection-simple} drawing.}
\reference Ringel~\cite{R64}, Gr\"{u}nbaum~\cite{G72b}.
\comments In a 1972 paper, Gr\"{u}nbaum~\cite{G72b} expresses surprise that $\maxcro(K_n)$ and $\maxcro(K_{m,n})$ have not been studied; he mentions $\maxcro(K_4) = 1$ and Saaty's claim that $\maxcro(K_n) = {n \choose 4}$~\cite{S69} which he calls ``probably true but unsubstantiated''. Ringel had already settled this problem earlier~\cite{R64}. This crossing number has also been called {\em maximal crossing number\index{maximal crossing number}}~\cite{G72b}.
\complexity Open.
\relations $\maxrcr(G) \leq \maxcro(G)$\index{maximum rectilinear crossing number} for all graphs $G$. $\maxcro(G) \leq M(G)$, where
$M(G) = \left(m(m+1) - \sum_{v \in V} \deg^2(v)\right)/2$, with $m = |E|$, a parameter introduced in~\cite{PRS91}.
\values $\maxcro(K_n) = {n \choose 4}$~\cite{R64}. $\maxcro(K_{x_1, \ldots, x_n}) = {x \choose 4} - \sum_{i=1}^n ({x_i \choose 4} + (x - x_i) {x_i \choose 3} )$, where $x = \sum_{i=1}^n x_i$ and $n \geq 2$~\cite{H76}. For trees $T$, $\maxcro(T) = M(T)$, with $M(T)$ as defined above~\cite{PRS91}. $\maxcro(C_4) = 1$, and $\maxcro(C_n) = n(n-3)/2$, for $n \neq 5$~\cite{W71}. $\maxcro(Q_3) = 36$, where $Q_3$ is the $3$-dimensional hypercube graph~\cite{H91}. Asymptotically, $\maxcro(W_n)$ is $5n^2/4$~\cite{HZ95}. Also, $\maxcro$ is known for all graphs on up to $6$ vertices~\cite{HZ95}.
\openq Ringeisen, Stueckle, and Piazza~\cite{RSP91} introduced the {\em Subgraph Problem}: is it true that $\maxcro(H) \leq \maxcro(G)$ if $H$ is a subgraph of $G$? Archdeacon~\cite{A09} conjectures that it is. The conjecture is unsettled even for induced subgraphs $H$ of $G$. For the maximum rectilinear crossing number, it is easy to see that $\maxrcr(H) \leq \maxrcr(G)$ if $H$ is a subgraph of $G$~\cite{RSP91}. The same authors also conjecture that $\maxcro(G) = M(G)$ if and only if $G$ contains at most one cycle and that cycle is not $C_4$, where $M(G)$ is as defined above. This conjecture is equivalent to Conway's thrackle conjecture, according to which every graph for which $\maxcro(G) = M(G)$ satisfies $|E(G)| \leq |V(G)|$~\cite{W71}.
\also Maximum rectilinear crossing number.
\end{cn}

\entry{Maximum orchard crossing number} See orchard crossing number.

\begin{cn}{Maximum rectilinear crossing number}\mindex{maximum rectilinear crossing number}
\defn The {\em maximum rectilinear crossing number} of a graph $G$, $\maxrcr(G)$, is the largest number of crossings in any simple straight-line drawing of $G$ (by requiring the graph to be simple we avoid edge overlap). If we restrict drawings to be convex (all vertices on the boundary of a circle), we get the {\em convex maximum rectilinear crossing number}\mindex{convex maximum rectilinear crossing number}, here denoted by $\maxrcr^{\circ}(G)$.
\reference Gr\"{u}nbaum~\cite{G72b}. Also, Furry, Kleitman~\cite{FK76}.
\comments Originally defined by Gr\"{u}nbaum who mentions several results, including the calculation of $\maxrcr(C_n)$ due to Steinitz~\cite{S23}.\footnote{Steinitz's result from 1923 was preceded by several incorrect or incomplete results, including a note by Baltzer~\cite{B1885} who seems to have originated the problem in 1885; in turn, it was rediscovered multiple times, e.g. in~\cite{FK76}.} Other names for this crossing number include {\em maximal rectilinear crossing number\index{maximal rectilinear crossing number}}~\cite{G72b} and {\em obfuscation complexity\index{obfuscation complexity}}~\cite{V08}. Verbitsky writes $\obf(G)$ for $\maxrcr$ and $\obf^{\circ}$ for $\maxrcr^{\circ}$.  Th\"{u}rmann~\cite{T00} considers a variant of $\maxrcr$ parameterized by an upper bound on the number of vertices that may lie on the boundary of the convex hull of all vertices.
\complexity Open, but can be approximated efficiently to within a factor of $56/39$~\cite{KPRSV08}.
\relations $\maxrcr(G) < 3 |V(G)|^2$~\cite{V08}. $\maxrcr(G) \leq \maxcro(G)$\index{maximum crossing number} (by definition) and the inequality can be strict (e.g.\ compare Steinitz's result on $\maxrcr(C_n)$ to $\maxcro(C_n)$ when $n$ is even).
\values $\maxrcr(K_{x_1, \ldots, x_n}) = {x \choose 4} - \sum_{i=1}^n ({x_i \choose 4} + (x - x_i) {x_i \choose 3} )$, where $x = \sum_{i=1}^n x_i$ and $n \geq 2$ (follows from~\cite{H76}, also see~\cite{AFI11}). $\maxrcr(C_n) = n(n-3)/2$ if $n$ is odd and $\maxrcr(C_n) = n(n-4)/2 + 1$ if $n$ is even~\cite{S23}.
$\maxrcr(W_n) = (2n^2-5n-1)/2$ if $n$ is odd and $n^2-3n+1$ if $n$ is even~\cite{F11}; for generalized wheel graphs $W_{m,n}$ see~\cite{AFI11}. $\maxrcr(Q_3) = 28$, where $Q_3$ is the $3$-dimensional hypercube graph~\cite{AFH09}. $\maxrcr(\mathrm{GP}(2,5)) = 49$~\cite{FHHK10}, where $\mathrm{GP}(2,5)$ is the Petersen graph. Calculating $\maxrcr(nP_2)$, the largest number of crossings of $n$ line segments, is an old puzzle, as in Sam Loyd Jr's ``When Drummers Meet'', see~\cite[5.Q.1]{S04x}, also known in textbooks~\cite[p.5, 3rd part]{K1889}, and, with variations, in~\cite{S1893}.
\openq Is it true that $\maxrcr(G) = \maxrcr^{\circ}(G)$\index{convex maximum rectilinear crossing number} for every graph $G$ as conjectured by Alpert, Feder and Harborth~\cite{AFH09}.
\also Maximum crossing number, convex crossing number.
\end{cn}

\begin{cn}{Metro-line crossing number}\mindex{Metro-line crossing number}
\defn Let $G$ be a graph embedded in the plane, and ${\cal L}$ a set of paths (without repeated vertices) in $G$ called {\em lines}. A {\em routing} of the lines orders all lines passing through an edge {\em at each end} of the edge. An {\em edge crossing} of two lines occurs if the ordering of the two lines at the two ends of some edge have switched. A vertex ({\em station}) is represented as a (convex) polygon with one side for each incident edge. The routing determines the order at each side of the station. If the entry and exit points of two lines alternate along the boundary of a station, a {\em station crossing} occurs; that is, the two lines have to cross within the station. The {\em Metro-line crossing number} of a particular routing of ${\cal L}$ in the embedding of $G$ is the number of edge and station crossings of lines in edges. The {\em Metro-line crossing number} of ${\cal L}$ is the smallest Metro-line crossing number of any routing of {\cal L}.\footnote{One can distinguish between avoidable and unavoidable station crossings: two lines entering a station through the same edge need not cross within the station, such a crossing can always be turned into an edge crossing without increasing the Metro-line crossing number of the drawing. Since the unavoidable station crossings can be computed in polynomial time, several papers restrict themselves to drawings without avoidable station crossings, and then only count edge crossings. This also gives a more interesting variant if one studies fixed-parameter tractability.}
\reference Based on Benkert, N{\"o}llenburg, Uno, Wolff~\cite{BNUW07}, Argyriou, Bekos, Kaufmann, Symvonis~\cite{ABKS10}.
\comments The concept of metro-line crossing minimization was introduced in Benkert, N{\"o}llenburg, Uno, Wolff~\cite{BNUW07}, a more general model was suggested by Argyriou, Bekos, Kaufmann, Symvonis~\cite{ABKS10}. Both these papers consider the problem a crossing minimization problem and study it in various variants (e.g. stations have to be $2$-sided or $4$-sided or the end of lines may be forced to be in particular positions), so the metro-line crossing number defined above is just one possible variant.
\complexity Optimizing the Metro-line crossing number of a single edge in $G$ can be done in polynomial time~\cite{BNUW07} and there are \NP-hard variants even if the underlying graph is a path~\cite{ABKS10} or a caterpillar~\cite{FP13a}. There are polynomial-time and fixed-parameter tractable cases for some variants~\cite{OTU13}.
\also Confluent crossing number, wire crossing number.
\end{cn}

\entry{Minimum non-crossing edge number} See edge crossing number.

\begin{cn}{Minor crossing number}\mindex{minor crossing number}
\defn The {\em minor crossing number}, $\mcr(G)$, of a graph $G$ is the smallest crossing number of any graph having $G$ as a minor. The {\em major crossing number}\mindex{major crossing number}, $\Mcr(G)$, of a graph $G$ is the largest crossing number of any minor of $G$. We write $\mcr_{\Sigma}$ for the minor crossing number on surface $\Sigma$.
\reference Bokal, Fijav{\v{z}}, Mohar~\cite{BFM06}.
\comments The definition of the minor crossing number was motivated by an attempt to find a crossing number that works well with minors, indeed it is minor-monotone by definition (the genus crossing number also addresses this issue), and is sometimes called the {\em minor monotone crossing number}. Robertson and Seymour identified the $41$ forbidden minors of the set $\{G: \mcr(G) \leq 1\}$~\cite{BFM06}. Chimani and Gutwenger~\cite{CG07} introduce a variant $\mcr_W(G)$, for $W \subseteq V(G)$, in which only vertices in $W$ are allowed to be expanded in the minor relationship; this allows them to draw connections to a hypergraph crossing number variant\index{hypergraph crossing numbers}.
\complexity \NP-complete~\cite{H06,PSS09d}.\footnote{Neither of those sources shows that the problem lies in \NP. For that one needs to observe that for every $G$ there is a graph $H$ so that $\mcr(G) = \cro(H)$ and $G$ can be obtained from $H$ using a polynomial (in size of $G$) number of contractions and deletions.} Testing $\mcr(G) \leq k$ is in polynomial time for any fixed $k$, since the property is closed under minors. However, only for $k=1$ is the set of forbidden minors known~\cite{BFM06}.
\relations $\mcr_{\Sigma}(H) \leq \mcr_{\Sigma}(G)$ if $H$ is a minor of $G$ (from definition), $\mcr_{\Sigma}(G) \leq \cro_{\Sigma}(G) \leq \Mcr_{\Sigma}(G)$ (from definition). $\cro_{\Sigma}(G) \leq \lfloor \Delta/2 \rfloor^2 \mcr_{\Sigma}(G)$~\cite{BFM06}, where $\Delta$ is the maximum degree of $G$. $\mcr_{\Sigma}(G) \geq (m-(3(n+g(\Sigma)) + 6))/2$, where $g(\Sigma)$ is the Euler genus of $\Sigma$ and $n = |V(G)|, m = |E(G)|$~\cite{BFM06}. There is a constant $c(H)$ for every graph $H$ so that $\mcr(G) \leq c(H) |V(G)|$ for every $G$ that does not contain $H$ as a minor~\cite{BFW08}.
\values $\mcr(K_n)$ is known for $n \leq 8$~\cite{BFM06}. There are asymptotic bounds for complete graphs, complete bipartite graphs and hypercubes~\cite{BFM06,BCSV10}.
\also Genus crossing number.
\end{cn}

\entry{Minor-monotone crossing number} Alternative name for minor crossing number.

\entry{Monotone crossing number} See monotone crossing numbers.

\begin{cn}{Monotone crossing numbers}\mindex{monotone crossing numbers}
\defn A drawing is {\em monotone} if every vertical line in the plane intersects each edge at most once. The {\em monotone crossing number} of $G$, $\mcro(G)$, is the smallest number of crossings in a monotone drawing of $G$. If $G$ is equipped with a preorder $\preceq$ (reflexive and transitive) of its vertices we restrict the drawings of $G$ to drawings which {\em respect} the preorder $\preceq$ in the sense that the total preorder created by the $x$-coordinates of the vertices extends $\preceq$. We write $\mcro_{\preceq}(G)$ for the resulting (fixed) monotone crossing number\mindex{fixed monotone crossing number}. If there is no danger of confusion, we will drop $\preceq$ in the notation.
If $\preceq$ is the trivial preorder, then $\mcro_{\preceq}$ is simply the monotone crossing number $\mcro$\mindex{monotone crossing number}; if $\preceq$ is a total preorder we get the {\em leveled crossing number}\mindex{leveled crossing number}\footnote{More typically called the multi-level crossing minimization problem. A {\em level} is a set of vertices that are equivalent in the sense that $u \preceq v$ and $v \preceq u$. Levels realized as parallel lines in a drawing are often called {\em layers}. In crossing minimization problems the first step typically consists in assigning vertices to layers and then ordering the vertices within each layer. One can consider crossing number variants in which orderings of some layers are already specified. E.g.\ in the well-known {\em one-sided crossing minimization problem} the bipartite graph is drawn on two layers and the ordering of one layer is pre-specified.}
 of which the bipartite crossing number\index{bipartite crossing number} and the $k$-layer crossing number\index{k layer crossing number@$k$-layer crossing number} are special cases. If $\preceq$ is a total order (at most one vertex per level, by anti-symmetry), we get the {\em $x$-monotone crossing number}\mindex{x-monotone crossing number@$x$-monotone crossing number}. For a directed acyclic graph $G$ with its induced preorder $\preceq$ we get the {\em upward crossing number}\mindex{upward crossing number} as $\mcro_{\preceq}(G)$.

For any crossing number notion $\cf$ one can introduce the corresponding monotone version $\mf$\mindex{monotone crossing numbers} as above (with or without a given preorder), for example, one can talk about the {\em monotone pair crossing number}\mindex{monotone pair crossing number}, $\mpcr$ or the {\em monotone odd crossing number}, $\mocr$\mindex{monotone odd crossing number}.
\reference Valtr~\cite{V04}, Fulek, Pelsmajer, Schaefer, \v{S}tefankovi\v{c}~\cite{FPSS12b}.
\comments The monotone crossing number\index{monotone crossing number} was introduced by Valtr~\cite{V04} who also mentions monotone pair crossing number\index{monotone pair crossing number} and monotone odd crossing number\index{monotone odd crossing number}. The preorder versions are introduced in~\cite{FPSS12b}, but many of these problems are implicit in the crossing minimization problems studied in leveled (layered) graph drawing. The preorder version $\mcro_{\preceq}$ suggested here is a general tool to unify many of these notions. One could imagine a bi-monotone crossing number\index{bi-monotone crossing number} in which orderings are prescribed both for the $x$ and the $y$ direction. Balko, Fulek, and Kyn{\v c}l~\cite{BFK13} introduce the {\em monotone odd $+$ crossing number}, $\mocr_{+}$\mindex{monotone odd plus crossing number@monotone odd $+$ crossing number} (under the name {\em monotone semisimple odd crossing number}\index{monotone semisimple odd crossing number}), and the {\em monotone odd $\pm$ crossing number}, $\ocr_{\pm}$\mindex{monotone odd plus minus crossing number@monotone odd $\pm$ crossing number} (using the name {\em monotone weakly semisimple odd crossing number}\index{monotone weakly semisimple odd crossing number}).
\complexity $\mcro(G)$ is \NP-complete.\footnote{\NP-hardness follows from the hardness of crossing number~\cite{GJ83}, simply subdivide each edge sufficiently often so each part can be drawn as a monotone edge. The problem lies in \NP: guess an ordering of the vertices and the ordering in which edges pass above and below each vertex. That is sufficient to calculate the crossing number of the drawing.} With two levels, crossing minimization is \NP-complete (see bipartite crossing number\index{bipartite crossing number} for a discussion), even if the ordering of one level is given (one-sided crossing minimization)~\cite{EMKW86,EW94}. Testing whether a directed graph has upward crossing number\index{upward crossing number} $0$ is \NP-complete~\cite{EK01}.

\relations $\cro(G) \leq \mcro(G) \leq \rcr(G)$\index{crossing number}\index{rectilinear crossing number} (definition). $\mcro(G) \leq 4 \mpcr(G)^{4/3}$\index{monotone pair crossing number} for all $G$~\cite{V04}. $\miocr(G) \leq \mocr(G) \leq \mocr_{\pm}(G) \leq \mocr_{+}(G) \leq \mcro(G)$ (definition). $\mcro(G) \leq {2\cro(G) \choose 2}$\index{monotone crossing number}, and there are graphs $G$ for which $\mcro(G) \geq 7/6\cro(G) - 6$~\cite{PT112}. If there is a graph $G$ with a linear order $\preceq$ of its vertices so that 
$\mf_{\preceq}(G) < \mg_{\preceq}(G)$ for 
$\cf, \cg \in \{\ocr, \iocr, \acr, \iacr, \pcr_+, \pcr, \pcr_-,$ $\cro,\cro_-\}$, 
then there is a graph $G'$ for which $\cf(G') < \cg(G')$; there is a graph $G$ with a linear order $\preceq$ of its vertices, so that $\miocr_{\preceq}(G) < \mocr_{\preceq}(G)$\index{monotone independent odd crossing number}\index{monotone odd crossing number} and consequently, there is a graph $G'$ so that $\iocr(G) < \ocr(G)$\index{independent odd crossing number}\index{odd crossing number}~\cite{FPSS12b}.
\values $\mcro(K_n) = Z(n)$~\cite{AAFMRS13a,AAFMRS13b}, where $Z(n) = X(n)X(n-2)/4$ is Zarankiewicz's function, with $X(n) = \lfloor n/2 \rfloor \lfloor (n-1)/2\rfloor$.\footnote{The result remains true if the edges in the drawing are only {\em $x$-bounded}, that is, each edge lies (horizontally) entirely between its endpoints.} The same result was also found by~\cite{BFK13} who prove the stronger result $\mocr_{\pm}(K_n) = \mocr_{+}(K_n) = Z(n)$.
\openq Is $\miocr(K_n) = Z(n)$~\cite{BFK13}?
\also Bipartite crossing number, radial crossing number, upward crossing number, pseudolinear crossing number, local crossing number (bottleneck crossing minimization).
\end{cn}

\entry{Multiplanar crossing number} See $k$-planar crossing number.


\begin{cn}{Nodal crossing number}\mindex{nodal crossing number}
\defn Let $\cro_D(e)$ be the number of crossings involving $e$ in a drawing $D$. Let $\cro_D(v)$ be the sum
of $\cro_D(e)$ over all $e$ incident to $v$ . The {\em nodal crossing number} of a drawing $D$ of a graph $G$, $\ncr(D)$, is the largest $\cro_D(v)$ over all vertices of $G$. The {\em nodal crossing number} of $G$, $\ncr(G)$, is the minimum of $\ncr(D)$ over all drawings of $G$. For the nodal crossing number on a surface $\Sigma$, we write $\ncr_{\Sigma}$.
\reference Guy, Jenkyns, Schaer~\cite{GJS68}.
\comments The nodal toroidal crossing number\index{nodal toroidal crossing number}, $\ncr_{S_1}$ was introduced by Guy, Jenkyns, Schaer~\cite{GJS68}.
\complexity Open.
\relations $\lcr(G) \leq \ncr(G) \leq \cro(G)$\index{local crossing number}\index{crossing number} (by definition).
\values $\ncr_{S_1}(K_n)$ is known for $n \leq 9$, and there are asymptotic results for $\ncr_{S_1}(K_n)$~\cite{GJS68}.
\also Local crossing number, Simple crossing number.
\end{cn}

\entry{Non-crossing edge number} See edge crossing number.

\begin{cn}{Odd crossing number}\mindex{odd crossing number}
\defn The {\em odd crossing number} of $G$, $\ocr(G)$, is the smallest number of pairs of edges crossing an odd number of times in any drawing of $G$. The Rule $+$ variant of $\ocr$ is $\ocr_+(G)$\index{odd plus crossing number@odd $+$ crossing number}, the smallest number of pairs of edges crossing an odd number of times in any drawing of $G$ in which adjacent edges are forbidden to cross (called {\em semisimple} in~\cite{BFK13}). One can define an intermediate variant in which adjacent edges have to cross evenly (such drawings are called {\em weakly semisimple} in~\cite{BFK13}); denote this variant by $\ocr_{\pm}$\index{odd plus minus crossing number@odd $\pm$ crossing number}.\footnote{The $+$ rule for crossing numbers looks rather straightforward: we prohibit drawings in which adjacent edges cross. One may ask, however, in what sense of the word cross? The standard interpretation is that $\cro(e,f) = 0$ for all pairs of adjacent edges $e$ and $f$. But why not require that $\cf(e,f) = 0$ if we are considering the crossing number $\cf$? For $\cro$ and $\pcr$ (and $\rcr$, of course), this makes no difference, but for $\ocr$ and $\acr$ we get a new variant which we denote by $\cf_{\pm}$~\cite{FPSS12b}. By definition, $\cf \leq \cf_{\pm} \leq \cf_+$.}
\reference Pach, T\'{o}th~\cite{PT00}, also Levow~\cite{L72}.
\comments First explicitly defined (and named) by Pach and T\'{o}th~\cite{PT00}, although Levow~\cite{L72} deserves some credit; he realized that Tutte's algebraic theory of crossing number could be developed over binary fields (Wu developed a theory parallel to Tutte's over binary fields, but he didn't touch on the subject of crossing numbers); Levow defines a parameter that could be algebraic or odd crossing number (or, indeed, an independent version). His definition is not precise enough to decide.
\complexity \NP-complete~\cite{PT00} and remains \NP-complete if the graph is cubic or rotation system is given~\cite{PSS09d}. The problem is fixed-parameter tractable~\cite{PSS07c}.
\relations There is a crossing lemma, $\ocr(G) \geq 1/64 m^3/n^2$ for $m > 4n$~\cite{PT00}\footnote{See the section on crossing lemma variants in Section~\ref{sec:WCN}.}. $\iocr(G) \leq \ocr(G) \leq \ocr_{\pm} \leq \ocr_+(G)$\index{independent odd crossing number}\index{odd plus minus crossing number@odd $\pm$ crossing number}\index{odd plus crossing number@odd $+$ crossing number} for all graphs $G$ (by definition). $\ocr(G) \leq \acr(G) \leq \cro(G)$\index{algebraic crossing number} (by definition). $\ocr(G) = \cro(G)$\index{crossing number} if $\ocr(G) \leq 3$~\cite{PSS07d}. There are graphs for which $\ocr(G) < (\sqrt{3}/2+o(1)) \acr(G) = \pcr(G) = \cro(G)$)~\cite{PSS08}\index{pair crossing number}. $\ocr_{\Sigma}(G) \leq {2\cro_{\Sigma}(G) \choose 2}$ for all surfaces $\Sigma$, and $\ocr_{\Sigma}(G) = \cro_{\Sigma}(G)$ if $\ocr_{\Sigma}(G) \leq 2$ for all surfaces $\Sigma$~\cite{PSS09}.
\also Independent odd crossing number, algebraic crossing number, monotone crossing number (for monotone version).
\end{cn}

\begin{cn}{Orchard crossing number}\mindex{orchard crossing number}
\defn An {\em orchard drawing} of $G$ is a straight-line drawing of $G$ with vertices in general position to which are added straight (infinite) lines through every pair of vertices. The {\em orchard crossing number}, $\orccr(D)$, of an orchard drawing $D$ of $G$ is the total number of crossings between edges and lines (not counting the line an edge lies on). The {\em orchard crossing number} of $G$, $\orccr(G)$, is the smallest orchard crossing number of any orchard drawing of $G$. The {\em maximum orchard crossing number}\mindex{maximum orchard crossing number} of $G$ is the largest orchard crossing number of any orchard drawing of $G$.
\reference Feder, Garber~\cite{FG09}.
\comments One can also imagine a pseudoline version of the orchard crossing number. Replacing lines with line segments in the definition of the orchard crossing number leads to the {\em airport crossing number}\index{airport crossing number}~\cite{EKWY12}. For the airport crossing number, a non-rectilinear version may be of interest as well.
\complexity Open.
\relations $\rcr(G) \leq \orccr(G)/2$\index{rectilinear crossing number}~\cite{FG09} (since every edge crossing counts twice). The drawing maximizing the orchard crossing number of $K_n$ realizes $\rcr(K_n)$~\cite{FG09}.
\values $\orccr(K_{n,n}) = 4n {n \choose 3}$~\cite{FG11}. Further results are in~\cite{FG11b}.
\also Rectilinear crossing number
\end{cn}

\entry{Oriented crossing number} See joint crossing numbers.

\entry{Outerplanar crossing number} See convex crossing number.

\begin{cn}{Pair crossing number}\mindex{pair crossing number}
\defn The {\em pair crossing number} of $G$, $\pcr(G)$, is the smallest number of pairs of edges crossing in any drawing of $G$. The {\em independent pair crossing number}\mindex{independent pair crossing number} of $G$, $\pcr_-(G)$, is the smallest number of pairs of independent edges crossing in any drawing of $G$. The Rule $+$ variant of $\pcr$ is $\pcr_+(G)$, the smallest number of pairs of edges crossing in any drawing of $G$ in which adjacent edges are forbidden to cross.
\reference Mohar~(attributed in \cite{KM04}), Pach, T\'{o}th~\cite{PT00,PT00b}.
\comments According to Kolman and Matousek~\cite{KM04}, the pair crossing number was first explicitly introduced by Mohar who asked whether $\pcr = \cro$\index{crossing number} at an AMS Conference on topological graph theory in 1995. The first mention in print seems to be by Pach and T\'{o}th~\cite{PT00} (as the {\em pairwise crossing number}\index{pairwise crossing number}), who pointed out that crossing number is often defined as pair crossing number (whether intentionally or not), see Section~\ref{sec:WCN} for a discussion. The independent pair crossing number\index{independent pair crossing number} was also defined by Pach and T\'{o}th~\cite{PT00b}; Alon~\cite{A00} and Tao and Vu~\cite{TV06} discuss the crossing lemma holds for the independent pair crossing number\index{independent pair crossing number}.
\complexity The pair crossing number is \NP-complete~\cite{PT00,SSS03} and remains \NP-complete if the graph is cubic or rotation system is given~\cite{PSS09d}. The independent pair crossing number\index{independent pair crossing number} is also \NP-complete. The pair crossing number is fixed-parameter tractable~\cite{PSS07c}.
\relations There is a crossing lemma, $\pcr_-(G) \geq 1/64 m^3/n^2$\index{independent pair crossing number} for $m > 4n$~\cite{A00}\footnote{See the section on crossing lemma variants in Section~\ref{sec:WCN}.}. $\ocr(G) \leq \pcr(G) \leq \cro(G)$\index{odd crossing number}\index{crossing number}, $\pcr_-(G) \leq \pcr(G) \leq \pcr_+(G)$\index{monotone pair crossing number}\index{pair plus crossing number@pair $+$ crossing number} for all $G$. There are graphs $G$ for which $\ocr(G) < \pcr(G)$\index{odd crossing number}~\cite{PSS08}, indeed $\ocr(G) = \acr(G) \leq 0.855 \pcr(G)$\index{algebraic crossing number} is possible~\cite{T08}. Matousek~\cite{M13} showed that $\cro(G) = O(\pcr(G)^{3/2} \log^{2} \pcr(G))$\index{crossing number} using a proof by T\'{o}th~\cite{T12} with stronger bounds on the size of separators for string graphs. Earlier results using different techniques are due to Valtr and T\'{o}th~\cite{V04, T08}.
\end{cn}

\entry{Pair-of-pants crossing number} See map crossing number.

\entry{Pair string crossing number} See string crossing number.

\entry{Pairwise crossing number} See pair crossing number.

\entry{Projective plane crossing number} See crossing number.

\begin{cn}{Pseudolinear crossing number}\mindex{pseudolinear crossing number}
\defn A {\em pseudoline} is a simple closed curve in the projective plane that is non-separating. A {\em pseudoline arrangement} is a set of pseudolines so that each pair of pseudolines has exactly one point in common. A {\em pseudolinear drawing} of $G$ is a drawing of $G$ in the projective plane so that each edge lies on a pseudoline in a pseudoline arrangement. Edges are then called {\em pseudosegments}. The {\em pseudolinear crossing number} of $G$, $\pscr(G)$, is the smallest number of crossings between pseudosegments in a pseudolinear drawing of $G$.
\reference Balogh, Lea{\~n}os, Pan, Richter, and Salazar~\cite{P06,BLPRS07}.
\comments The pseudolinear crossing number was introduced in Pan's thesis~\cite{P06}.
\complexity \NP-complete~\cite{HVLS14}. It is \NPR-complete to test whether $\pscr(G) = \rcr(G)$~\cite{HVLS14}.
\relations $\mcro(G) \leq \pscr(G) \leq \rcr(G)$\index{monotone crossing number}\index{rectilinear crossing number} (since pseudolines can be realized as $x$-monotone curves and because every rectilinear drawing can be extended to a pseudoline drawing). The pseudolinear crossing number differs from the standard crossing number, even for complete graphs: $18 = \cro(K_8) < \pscr(K_8) = \rcr(K_8) = 19$. Hern\'{a}ndez-V\'{e}lez, Lea{\~n}os, Jes\'{u}s and Salazar~\cite{HVLS14} show that the graphs $G_m$ introduced by Bienstock and Dean~\cite{BD93} separate $\cro$ from the pseudolinear crossing number, since $\cro(G_m) = 4$ and $\pscr(G_m) = m$. This also separates $\mcro$ from $\pscr$ since $\mcro \leq {2 \cro \choose 2}$~\cite{PT112}. For every $m$ there is an $H_m$ so that $\pscr(H_m) \leq \rcr(H_m) - m$~\cite{HVLS14}.
\values $\pscr(K_n) = \rcr(K_n)$\index{rectilinear crossing number} for $n \leq 27$~\cite{AFMLS03,AFMLS08,ABFMLS08}.
$\pscr(K_n) \geq 0.379688 {n \choose 4}$. Some of the best asymptotic lower bounds for $\rcr(K_n)$ are achieved via $\pscr(K_n)$.
\openq Balogh, Lea{\~n}os, Pan, Richter, and Salazar~\cite{BLPRS07} conjecture that\linebreak
 $\pscr(K_n) = \rcr(K_n)$\index{rectilinear crossing number}.
\also Rectilinear crossing number, monotone crossing number.
\end{cn}

\begin{cn}{Radial crossing number}\mindex{radial crossing number}
\defn A {\em leveling} of a graph $G = (V,E)$ is a mapping from $V$ to $\{1,\ldots,k\}$, assigning each vertex a {\em level}. A {\em radial drawing} of $G$ is a drawing in which vertices of level $i$ are placed on the $i$th circle of $k$ concentric circles; edges are required to be monotone in the sense that they cross every circle that is concentric with the level circles at most once. The {\em radial crossing number} of $G$ is the smallest number of crossings in a radial drawing of $G$.
\reference Bachmaier~\cite{B07}. Richter, Thomassen~\cite{RT97}. Also, Northway~\cite{N40}.
\comments Bachmaier~\cite{B07} introduced the general concept of radial crossing number. If $G$ is bipartite one can assign the vertices of each partition to one of two circles, resulting in the bipartite cylindrical drawings introduced by Richter and Thomassen~\cite{RT97} to study the crossing number of $K_n$ via bipartite cylindrical drawings of $K_{n,n}$; there also is a concept of cylindrical crossing number\index{cylindrical crossing number} for non-bipartite graphs. In a paper from 1940, Northway~\cite{N40}, suggested radial layouts and used the number of crossing lines as an aesthetic criterion.
\complexity Radial level planarity can be tested in linear time~\cite{BBF05}. For two levels, the radial crossing number is \NP-complete (this easily follows from  \NP-hardness of the bipartite crossing number\index{bipartite crossing number}), as is the one-sided version (in which the ordering of the vertices on one level is fixed)~\cite{B07,EMKW86,EW94}. If orderings of vertices on both sides are fixed, the problem is in polynomial time~\cite{PSS09d}\footnote{In this case, the radial crossing number turns into the annulus crossing number\index{annulus crossing number}.}.
\relations The leveled crossing number\index{leveled crossing number} of $G$ is an upper bound on its radial crossing number. In particular, the bipartite crossing number\index{bipartite crossing number}, $\bcr$, is an upper bound on radial crossing number with two levels (the upper bound may be strict, e.g.\ for $K_{2,2}$).
\values The radial crossing number of $K_{n,n}$ on two levels is $n {n \choose 3}$~\cite{RT97}.
\also Bipartite crossing number, leveled crossing number (under monotone crossing numbers), annulus crossing number (under map crossing number), cylindrical crossing number.
\end{cn}

\begin{cn}{Rectilinear crossing number}\mindex{rectilinear crossing number}
\defn The {\em rectilinear crossing number} of $G$, $\rcr(G)$, is the smallest number of crossings in a straight-line drawing of $G$.
\reference Harary, Hill~\cite{HH63}.
\comments The rectilinear crossing number for arbitrary graphs was introduced by Harary and Hill~\cite{HH63}. It is sometimes claimed that the rectilinear crossing number is also known as the {\em linear}\index{linear crossing number} or {\em geometric(al)}\index{geometric(al) crossing number} crossing number, but evidence for that is slim.\footnote{If it is used at all, the term ``linear crossing number'' typically refers to the linear crossing number introduced by Nicholson, the only exceptions I found are~\cite{B97,A09}. The use of ``geometric drawing'' for straight-line drawing is quite common, but there only seem to be a small number of papers using the term geometric crossing number~\cite{A09,AFMS12}.}
\complexity \NPR-complete~\cite{B91}, see~\cite{S10b} for \NPR.
\relations $\cro(G) \leq \rcr(G)$\index{crossing number} for all graphs $G$, and inequality can be strict, e.g.\ $18 =\cro(K_8) < \rcr(K_8) = 19$~\cite{B70,S71}.\footnote{Barton's thesis~\cite{B70} and Singer's unpublished manuscript~\cite{S71} also contain early upper bounds on $\rcr(K_n)$, Barton obtains $\rcr(K_n) \leq 11/648 n^4 + O(n^3)$ and Singer shows $\rcr(K_n) \leq 5/312 n^4 + O(n^3)$; see the section on values for current best bounds.} $\cro(G) = \rcr(G)$ if $\rcr(G) \leq 3$, but for every $k$ there is a $G$ such that $\cro(G) = 4$\index{crossing number} and $\rcr(G) \geq k$~\cite{BD93}\footnote{Some more light is thrown on these separating examples in~\cite{HVLS14}}. Also, $\rcr(G) = O(\Delta \cro^2(G))$, where $\Delta$ is the maximum degree of $G$~\cite{BD92}; this was improved to $\rcr(G) = O(\Delta \cro(G) \log \cro(G))$ if $|E| \geq 4|V|$~\cite{SSSV95}. Wilf~\cite{W97} points out that $\rcr(G) \leq \rho M/3$, where $M$ is the number of times $2K_2$ occurs as a subgraph in $G$, and $\rho \approx 0.38$ is the rectilinear crossing constant\index{rectilinear crossing constant} (definition under values).\footnote{The paper doesn't supply an argument, but one imagines Wilf would have argued as follows: fix an $\rcr$-optimal drawing of $K_n$, where $n = |V(G)|$. Randomly assign vertices in $V(G)$ to vertices in the drawing of $K_n$. Then the probability that four vertices of $V(G)$ are in convex position, is $\rho {n \choose 4}$ by definition of $\rho$. The probability that two edges of $G$ are mapped to the four endpoints so that the two edges cross, is $1/3$; hence, the expected number of crossings of $G$ is at most $\rho M/3$. }
\values The values of $\rcr(K_n)$ are now known up to $n=27$ and for $n = 30$ (see~\cite{AFMS12} for a recent survey, also~\cite{A13}). $\rcr(K_n) > \cro(K_n)$ for $n=8$ and $n \geq 10$. $41/108 {n \choose 4} \leq \rcr(K_n) \leq 9363184/24609375 {n \choose 4} + \Theta(n^3)$ (lower bound:~\cite{AGOR07}, upper bound:~\cite{FML14}; current techniques are described in~\cite{AFMS12}). Since $\rcr(K_n)/{n \choose 4}$ is nondecreasing and bounded, $\rho = \lim_{n \rightarrow \infty} \rcr(K_n)/{n \choose 4}$---sometimes called the {\em rectilinear crossing constant}~\cite{F03}\mindex{rectilinear crossing constant}---exists, and is, surprisingly, related to Sylvester's Four Point Problem~\cite{SW94}.
For complete bipartite $\rcr(K_{m,n}) \leq Z(m,n)$, where $Z(m,n) = X(m)X(n)$ and $X(n) = \lfloor n/2 \rfloor \lfloor (n-1)/2\rfloor$~\cite{Z53}. It has been conjectured that $\rcr(K_{m,n}) = \cro(K_{m,n})$~\cite{A09}. This conjecture is implied by Zarankiewicz's conjecture as Guy observed~\cite{G71}.
$\rcr(C_3 \times C_n) = n$~\cite{RB78}, $\rcr(C_4 \times C_n) = 2n$~\cite{BR80}. For complements of cycles, see~\cite{GH73}. Faria, de Figueiredo, Richter and Vr{\v{t}}o~\cite{FdFRV13} give upper bounds on $\rcr(Q_n)$.
\openq Harary, Kainen, and Schwenk conjectured that $\cro(C_m \times C_n) = n(m-2)$\index{monotone odd crossing number} for $n \geq m \geq 3$; since there are straight-line drawings of $C_m \times C_n$ with $n(m-2)$ crossings, a weaker conjecture would be: $\rcr(C_m \times C_n) = n(m-2)$ for $n \geq m \geq 3$; the conjecture is known to be true for the same cases as the original conjecture which is discussed in the entry on the crossing number. The separation of $\cro$ and $\rcr$ by Bienstock and Dean~\cite{BD93} implies that $\rcr$ cannot be bounded in $\cro$; however, Hern\'{a}ndez-V\'{e}lez, Lea{\~n}os, Jes\'{u}s and Salazar~\cite{HVLS14} conjecture that this can be done, that is, $\cro(G) \leq f(\rcr(G))$\index{crossing number} for some function $f$, as long as $G$ is $3$-connected.
\also $t$-polygonal crossing number, pseudolinear crossing number, maximum rectilinear crossing number, simultaneous geometric crossing number (under simultaneous crossing number), grid crossing number, rectilinear local crossing number (under local crossing number).
\end{cn}

\entry{Rectilinear edge crossing number} See edge crossing number.

\entry{Rectilinear local crossing number} See local crossing number.

\entry{Rectilinear space crossing number} See space crossing number.

\begin{cn}{Red/blue crossing number}\mindex{red/blue crossing number}
\defn Given graphs $G_i = (V_i, E_i)$, and point-sets $P_i$ in the Euclidean plane with $|P_i| = |V_i|$, $i \in \{1,2\}$, a {\em red/blue} drawing consists of straight-line embeddings of $G_i$ on vertex set $P_i$, $i \in \{1,2\}$ (each graph by itself is free of crossings). The {\em red/blue crossing number} is the smallest number of crossings in a red/blue drawing (necessarily between edges of $G_1$, the red edges, and $G_2$, the blue edges; in other words, we count red/blue crossings). It is possible that the $G_i$ have no red/blue drawing on the $P_i$, in which case we say that the red/blue crossing number is infinite.
\reference Based on Bereg, Jiang, Yang, Zhu~\cite{BJYZ11}.
\comments Bereg, Jiang, Yang, Zhu~\cite{BJYZ11} are interested in the smallest number of crossings between any two crossing-free, geometric spanning trees on $P_1$ and $P_2$. However, they do go on to study the special case where the $G_i$ are paths.
\complexity Testing whether the red/blue crossing number of two paths is $0$ is \NP-complete~\cite{BJYZ11}. (Finding red/blue spanning trees with the minimum number of crossings can be solved in time $O(n \log n)$.)
%\relations
\also Simultaneous crossing number, joint crossing numbers.
\end{cn}

\begin{cn}{Right-angle crossing number}\mindex{right-angle crossing number}
\defn The {\em right-angle crossing number} of $G$ is the smallest number of crossings in a straight-line drawing of $G$ in which all pairs of crossing edges have to be orthogonal. If no such drawing exists, the right-angle crossing number is infinite.
\reference Based on Didimo, Eades, and Liotta~\cite{DEL11}.
\comments Didimo, Eades, and Liotta~\cite{DEL11} introduced the notion of RAC (Right Angle Crossing) drawing based on the aesthetic heuristic that drawings are easier to read if angles at crossings are large~\cite{HHE08}. One can imagine a $t$-polygonal right-angle crossing number, in which each edge is allowed to consist of $t$ line segments. Didimo, Eades, and Liotta~\cite{DEL11} showed that every graph has finite $4$-polygonal right-angle crossing number\index{t polygonal right-angle crossing number@$t$-polygonal right-angle crossing number}. A more relaxed version may only require angles to be at least some large $\alpha \leq 90$, see~\cite{DGDLM11,DGMW11}\index{large angle crossing number}.
\complexity It is \NP-hard to decide whether a graph has finite right-angle crossing number~\cite{ABS11}. It is not unlikely that this problem may be \NPR-complete (see~\cite{S10b} for \NPR).
\relations The right-angle crossing number of $G$ is at least $\rcr(G)$. If $G$ has finite right-angle crossing number, then $m \leq 4n-10$ assuming that $n \geq 4$~\cite{DEL11}.
\end{cn}

\entry{Rotational crossing number} Crossing number of graph with rotation (or embedding) system. See entry for crossing number.

\begin{cn}{Simple crossing number}\mindex{simple crossing number}
\defn The {\em simple crossing number} of $G$, $\cro^{\times}(G)$, is the smallest number of crossings in any drawing of $G$ in which every edge has at most one crossing.\footnote{Ringel~\cite{R65} already observed that crossings between two adjacent edges can always be removed in such a drawing.} If there is no such drawing, we let $\cro^{\times}(G) = \infty$; the name ``simple crossing number'' conflicts with the usual notion of a simple drawing (which only requires that every two edges cross at most once). Kainen~\cite{K74} called a drawing in which every edge has at most one crossing {\em nearly planar}, Ringel~\cite{R81} called it a {\em $1$-embedding}; the graphs with $\cro^{\times}(G) \leq 1$ are called {\em $1$-planar}~\cite{S86}\mindex{1-planar}.
\reference Buchheim, Ebner, J{\"u}nger, Klau, Mutzel, Weiskircher~\cite{BEJKMW06}.
\comments Buchheim, Ebner, J{\"u}nger, Klau, Mutzel, Weiskircher~\cite{BEJKMW06} introduce this variant to simplify their integer linear program for crossing minimization; the usefulness of the simple crossing number lies in the fact that every graph $G$ has a subdivision $G'$ for which $\cro(G) = \cro^{\times}(G')$. $1$-planar graphs can be $6$-colored~\cite{R65,B95} (in principle) and $7$-colored in linear time~\cite{CK03}.
\complexity Deciding whether $\cro^{\times}(G) < \infty$ is \NP-complete~\cite{BG07}.
\relations $\cro^{\times}(G) < \infty$ is equivalent to $\lcr(G) \leq 1$\index{local crossing number}. If $\cro^{\times}(G) < \infty$, then $m \leq 4n-8$ and $\cro^{\times}(G) \leq n-2$~\cite{BSW83}.\footnote{The result that any $1$-planar drawing of a graph $G$ on $n$ vertices has at most $n-2$ crossings is implicit in several papers, e.g.~\cite{BSW83,FM07}, an explicit statement can be found in~\cite{CH13}.}
\also Local crossing number.
\end{cn}

\entry{Simple degenerate crossing number} See degenerate crossing number.
\entry{Simple degenerate local crossing number} See local crossing number.

\entry{Simple local crossing number} See local crossing number.

\begin{cn}{Simultaneous crossing number}\mindex{simultaneous crossing number}
\defn A {\em simultaneous drawing} of a family of graphs ${\cal G} = (G_i)_{i=1}^k$, with $G_i = (V_i,E_i)$, is a drawing of $G = (V,E)$ with $V = \bigcup_{i=1}^k V_i$ and $E = \bigcup_{i=1}^k$. In other words, vertices or edges that belong to more than one graph are drawn only once. There are two different types of crossings in the drawing of $G$: a {\em proper crossing} is a crossing between two edges $e$ and $f$ that belong to the same graph $G_i$ for some $i$, otherwise the crossing is a {\em phantom crossing}. The {\em simultaneous crossing number} of ${\cal G}$, $\scr({\cal G})$, of a family of graphs ${\cal G} = (G_i)_{i=1}^k$ is the smallest number of proper crossings in any simultaneous drawing of $G$ as defined above. A proper crossing of two edges $e$ and $f$ counts once for each graph $G_i$ in which it occurs. A family of graphs is {\em simultaneous planar} if $\scr({\cal G}) = 0$. If we restrict the drawings to be straight-line drawings, we get the {\em simultaneous geometric crossing number}\mindex{simultaneous geometric crossing number} of $G$, $\sgcr$. If we restrict the drawings to be convex (all vertices on the boundary of a disk, all edges inside the disk), we get the {\em convex simultaneous crossing number}\mindex{convex simultaneous crossing number}.
\reference Chimani, J{\"u}nger, Schulz~\cite{CJS08}, He, S{\u{a}}l{\u{a}}gean,and M{\"a}kinen~\cite{HSM10}.
\comments The crossing number $\scr({\cal G})$ was introduced in Chimani, J{\"u}nger, Schulz along with several minimization problems, including the minimization of phantom crossings in an $\scr$-minimal drawing. Chimani, J{\"u}nger, Schulz also consider a weighted variant which is still restricted to counting only proper crossings. One could consider a more general variant in which phantom crossings are assigned weights. The restriction to drawings in which edges belonging to more than one graph are drawn only once is typically known as the {\em simultaneous embedding with fixed edges (SEFE)} style (an unfortunate name). When defining the crossing number version, the {\em fixed edges} epithet was dropped. One could consider defining a {\em free} version in which edges belonging to multiple graphs may be drawn differently for each graph. The convex simultaneous crossing number\index{convex simultaneous crossing number} is based on an observation by He, S{\u{a}}l{\u{a}}gean,and M{\"a}kinen~\cite{HSM10} which implies that it corresponds to a book drawing in which edges belonging to the same $G_i$ are assigned to the same page. It extends the partitioned book crossing number\index{partitioned book crossing number}; it is more powerful, since in an edge in a simultaneous drawing can belong to multiple graphs.
\complexity \NP-complete~\cite{CJS08}.\footnote{\NP-hardness follows since for $k=1$ $\scr$ is the same as $\cro$. \NP-membership is non-trivial for $k>1$~\cite{SSS08}.} Testing simultaneous planarity is \NP-complete for three graphs (the complexity of testing simultaneous planarity of two graphs is open)~\cite{GJPSS06}. The convex simultaneous crossing number generalizes the convex crossing number and therefore is \NP-complete. Testing convex simultaneous planarity is \NP-complete if the number of graphs $k$ is not bounded~\cite{H12}; it is open whether the problem remains \NP-complete for fixed $k$.
\relations $\scr({\cal G}) \leq k \cro(G)$\index{crossing number}, where $G = (V,E)$ with $V = \bigcup_{i=1}^k V_i$ and $E = \bigcup_{i=1}^k E_i$~\cite{CJS08}. The number of phantom crossings in an $\scr$-minimal drawing can be forced to be exponential~\cite{CJS08}, though it is not clear whether this is true for fixed $k$; the case
$k=2$ would be particularly interesting.
The top picture in the margin
\marginpar{
\begin{pspicture}(0,0)(60,40)
\cnode*(0,0){1pt}{v1}
\cnode*(30,0){1pt}{v2}
\cnode*(60,0){1pt}{v3}
\cnode*(60,20){1pt}{v4}
\cnode*(60,40){1pt}{v5}
\cnode*(45,40){1pt}{v6}
\cnode*(15,40){1pt}{v7}
\cnode*(0,40){1pt}{v8}
\cnode*(0,20){1pt}{v9}
\cnode*(30,20){1pt}{v0}

\ncline{v1}{v3}
\ncline{v3}{v5}
\ncline{v5}{v8}
\ncline{v8}{v1}

\ncline[linewidth=0.3, linecolor = red]{v9}{v0}
\ncline[linewidth=0.3, linecolor = green]{v0}{v4}

\nccurve[linewidth=0.3,angleA=120, angleB=-135,ncurv = 1.5,linecolor = green]{v2}{v6}
\nccurve[linewidth=0.3,angleA=60, angleB=-45, ncurv = 1.5, linecolor = red]{v2}{v7}

\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9a}{v9g}
\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9b}{v9f}
\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9c}{v9e}

\nccurve[linewidth=0.3,angleA=-90, angleB=-90]{v6a}{v6e}
\nccurve[linewidth=0.3,angleA=-90, angleB=-90]{v6b}{v6d}

\end{pspicture}
}
shows that for $k=2$ adjacent edges may have to cross in an embedding; a simple modification shown just below
\marginpar{
\begin{pspicture}(0,0)(60,40)
\cnode*(0,0){1pt}{v1}
\cnode*(15,0){1pt}{v2a}
\cnode*(45,0){1pt}{v2b}
\cnode*(60,0){1pt}{v3}
\cnode*(60,20){1pt}{v4}
\cnode*(60,40){1pt}{v5}
\cnode*(45,40){1pt}{v6}
\cnode*(15,40){1pt}{v7}
\cnode*(0,40){1pt}{v8}
\cnode*(0,20){1pt}{v9}
\cnode*(30,20){1pt}{v0}

\ncline{v1}{v3}
\ncline{v3}{v5}
\ncline{v5}{v8}
\ncline{v8}{v1}

\ncline[linewidth=0.3, linecolor = red]{v9}{v0}
\ncline[linewidth=0.3, linecolor = green]{v0}{v4}

\nccurve[linewidth=0.3,angleA=150, angleB=-150,ncurv = 2,linecolor = green]{v2b}{v6}
\nccurve[linewidth=0.3,angleA=30, angleB=-30, ncurv = 2, linecolor = red]{v2a}{v7}

\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9a}{v9g}
\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9b}{v9f}
\nccurve[linewidth=0.3,angleA=0, angleB=0,ncurv=0.7]{v9c}{v9e}

\nccurve[linewidth=0.3,angleA=-90, angleB=-90]{v6a}{v6e}
\nccurve[linewidth=0.3,angleA=-90, angleB=-90]{v6b}{v6d}

\end{pspicture}
}
shows that two independent edges may have to cross at least twice.\footnote{\label{foot:scrad} In both examples, there are two graphs: green and red, and the black edges belong to both the green and the red graph; the outer face is forced to be empty. These examples also show that not allowing adjacent or multiple phantom crossings can increase the simultaneous crossing number. The obvious generalizations of these examples, e.g.\ showing that two edges may be made to cross an arbitrary number of times, are incorrect.}
\also Red/blue crossing number, joint crossing numbers.
\end{cn}

\entry{Simultaneous geometric crossing number} See simultaneous crossing number.

\entry{Single-faced crossing number} See joint crossing numbers.

\begin{cn}{Space crossing number}\mindex{space crossing number}
\defn A {\em spatial drawing} of a graph $G$ is a continuous embedding of $G$ in $\RN^3$, it is {\em rectilinear} if edges are line segments. A {\em spatial crossing} is any (straight) line that crosses four\footnote{Bukh and Hubbard also, in passing, mention the possibility of counting lines that cross {\em three} edges.} vertex-disjoint edges. The {\em space crossing number} of $G$, $\spcr(G)$, is the smallest number of spatial crossings in any spatial drawing of $G$. The {\em rectilinear space crossing number}\mindex{rectilinear space crossing number}, $\rspcr(G)$, is the smallest number of spatial crossings in any rectilinear spatial drawing of $G$.
\reference Bukh, Hubard~\cite{BH11}.
\comments For a notion of crossing number for geometric hypergraphs, see~\cite{AS13}.
\complexity Open.
\relations $\spcr(G) \leq {\cro(G) \choose 2}$\index{crossing number}; for every $k$ there is a graph $G$ with $\spcr(G) = 0$ and $\cro(G) \geq k$~\cite{BH11}. There is a crossing lemma, $\spcr(G) \geq m^6 / (c n^4 \log^2 n)$ for $c=4^{179}$, and $n = |V|$, $m = |E|$ as long as $m \geq 4^{41} n$~\cite{BH11}.
\openq Bukh and Hubbard ask whether graphs with $\spcr(G) = 0$ are minor-closed and whether $\spcr(G) = 0$ is equivalent to $\rspcr(G) = 0$. They conjecture negative answers in both cases.
\also Grid crossing number.
\end{cn}

\entry{Spherical crossing number} See geodesic crossing number.

\begin{cn}{Spine crossing number}\mindex{spine crossing number}
\defn The {\em spine crossing number}\footnote{This crossing parameter has never been named, the closest is the occasional use of the phrase {\em crossings over the spine}. It has also been studied as a minimization problem for upward planar drawings~\cite{MS08}.} of $G$ in a book of $k$ pages is the smallest number of edges crossing the spine in a $k$-page topological book embedding of $G$. In a {\em topological book embedding} edges are allowed to cross the spine.
\reference Based on Miyauchi~\cite{M93}.
\comments Miyauchi gives an upper bound on the number of spine crossings for $K_n$ in a $3$-page book (also see discussion in the entry on book crossing number).
\complexity Open.
\relations The spine crossing number of a graph $G=(V,E)$ in a $(k+1)$-page book is at most $O(|E| \log_k |V|)$~\cite{EM99,M05}.
\also Book crossing number
\end{cn}

\begin{cn}{Stable crossing number}\mindex{stable crossing number}
\defn The {\em stable crossing number} of $G$ with parameter $k$ is $\cro_{\Sigma}(G)$ where $\Sigma = S_{\gamma(G) -k}$ and $\gamma(G)$ is the (orientable) genus of $G$.
\reference Kainen~\cite{K72b}.
\comments Kainen's motivation in introducing the stable crossing number seems to have been to investigate infinite families of graphs in surfaces in which they are nearly embeddable and show that this can lead to small constant (stable) crossing numbers~\cite[Abstract]{K72b}.
\complexity \NP-complete even for $k=1$, since determining the planar crossing number of a toroidal graph is \NP-complete, e.g. by the result of Cabello, Mohar~~\cite{CM10}.
\values $4k \leq \cro_{\Sigma}(Q_n) \leq 8k$ for $\Sigma = S_{\gamma(Q_n) - k}$ and $0 \leq k \leq \gamma(Q_n)$~\cite{K72b}. $\cro_{\Sigma} (Q_n \times K_{4,4}) = 4k$, where $0 \leq k \leq 2^n$, $\Sigma = S_{ \gamma(Q_n \times K_{4,4}) - k}$~\cite{KW78}.
\openq Kainen~\cite{K72b} conjectured $\cro_{\Sigma}(Q_n) = 8k$ for $\Sigma = S_{\gamma(Q_n) - k}$.
\end{cn}


\begin{cn}{String crossing number}\mindex{string crossing number}
\defn The {\em string crossing number} of $G$, $\strcr(G)$, is the smallest number of crossings in any string drawing of $G$ minus $|E(G)|$. A {\em string drawing} of $G$ is a set of curves $(c_v)_{v \in V(G)}$ so that $c_u$ and $c_v$ cross for every edge $uv \in E(G)$.\footnote{Crossings between $c_u$ and $c_v$ are allowed even if there is no edge $uv$; so a string drawing is not a string representation in the strict sense in which a string graph is the intersection graph of a set of curves in the plane. String graphs correspond to graphs of string crossing number $0$.}
\reference Bokal, Czabarka, Sz{\'e}kely, Vr{\v{t}}o~\cite{BCSV10}.
\comments  Bokal, Czabarka, Sz{\'e}kely, Vr{\v{t}}o~\cite{BCSV10} also suggest the {\em independent string crossing number}\mindex{independent string crossing number} (they call it the faithful crossing number) and the {\em pair string crossing number}\index{faithfull crossing number}. Richter, Thomassen~\cite{RT95} study a similar notion for closed curves in their proof that $\cro(C_5 \times C_5) = 15$.
\complexity Open.
\relations $\strcr_{\Sigma}(G) \leq 4 \mcr_{\Sigma}(G)$\index{minor crossing number}~\cite{BCSV10}.
\end{cn}

\entry{Surface crossing number} See crossing number.

\begin{cn}{$t$-polygonal crossing number}\mindex{t polygonal crossing number@$t$-polygonal crossing number}
\defn The {\em $t$-polygonal crossing number} of $G$, $\rcr_t(G)$, is the smallest number of crossings in a straight-line drawing of $G$ in which every edge is allowed to consist of up to $t$ line segments.
\reference Bienstock~\cite{B91}.
\comments Introduced by Bienstock~\cite{B91} to bridge the gap between $\cro$\index{crossing number} and $\rcr$\index{rectilinear crossing number}. In the area of graph drawing, $t$-polygonal drawings would also be called $(t-1)$-bend drawings (each edge having at most $t-1$ bends).
\complexity \NPR-complete~\cite{B91} for $t = 1$, see~\cite{S10b} for \NPR. Open for $t>1$.
\relations $\rcr_1(G) = \rcr(G)$ (by definition), $\rcr_2(G) \leq 2\cro(G)^2$~\cite{BD93}. Let $t(k)$ be the smallest $t$ so that $\rcr_t(G) = \cro(G)$ for all $G$ with $\cro(G) \leq k$. Then $t(k) = \Theta(k^{1/2})$~\cite{B91}.
\also Rectilinear crossing number.
\end{cn}

\begin{cn}{Tile crossing number}\mindex{tile crossing number}
\defn A {\em tile} $T$ is a graph $G = (V,E)$ together with two disjoint sequences $L = \{u_1, \ldots, u_k$\} and $R = \{v_1, \ldots, v_k\}$ of vertices in $V$. A {\em tile drawing} of $T$ is a drawing of $T$ in the unit square with all vertices of $L$ on the left boundary of the square in order, that is, $u_i$ above $u_{i+1}$, and all vertices of $R$ on the right boundary with $v_i$ above $v_{i+1}$. The {\em tile crossing number} of $T$ is the smallest number of crossings in a tile drawing of $T$. $T^2$ is the tile obtained from $T$ by placing two copies of $T$ next to each other and identifying $v_i$ of the left copy with $u_i$ of the right copy, for $1 \leq i \leq k$. This defines tiles $T^n$ for arbitrary integer powers $n$. The {\em average crossing number}\mindex{average crossing number} of $T$ is the limit of the tile crossing number of $T^n$ divided by $n$ as $n$ goes to infinity.
\reference Pinontoan, Richter~\cite{PR04b}.
\comments Pinontoan and Richter~\cite{PR04b} do not require that $|L| = |R|$, but they mostly study tiles they call self-compatible for which this is the case, since for those tiles the average crossing number\index{average crossing number} is defined. They can show that the average crossing number of a tile always exists. The tile crossing number is rather specific to constructions of crossing critical graphs. It bears similarity to bipartite and convex crossing number\index{bipartite crossing number}\index{convex crossing number}, but differs from them by allowing additional vertices within the square. In that respect, it resembles the anchored crossing number\index{anchored crossing number} most closely.
\complexity The tile crossing number is \NP-complete.\footnote{The regular crossing number\index{crossing number} is a special case for $k=0$.} If $L \cup R = V$, then the problem is in polynomial time. The complexity of the average crossing number is open.
\relations $\tilecr(T^n) \leq n \tilecr(T)$~\cite{PR04b}. Let $o(T^n)$ be the graph constructed from $T^n$ by identifying $L$ and $R$ of the tile $T^n$ (in order). Then the average crossing number of $T$ equals $\lim_{n\rightarrow \infty} \cro(o(T^n))/n$~\cite{PR04b}.
\openq Pinotoan and Richter~\cite{PR04b} conjecture that if the average crossing number of $T$ equals $\tilecr(T)$, then there is an $N$ so that $\cro(o(T^n))/n = \tilecr(T)$ for all $n \geq N$.
\also Anchored crossing number (under fixed linear crossing number), bipartite crossing number, convex crossing number.
\end{cn}

\entry{Toroidal crossing number} See crossing number.

\entry{Toroidal geodesic crossing number} See geodesic crossing number.

\begin{cn}{Triple crossing number}\mindex{triple crossing number}
\defn The {\em triple crossing number} of $G$, $\tricr(G)$, is the smallest number of triple crossings (a point in which three edges cross) in a drawing in which there are only triple crossings. We assume that there are no self-crossings, no crossings between adjacent edges, and that independent edges cross at most once and do not touch. The triple crossing number may be infinite.
\reference Tanaka, Teragaito~\cite{TT10}.
\comments As the definition shows, Tanaka, Teragaito~\cite{TT10} introduce a very restrictive version of a triple crossing number (which more accurately could be called the simple triple crossing number). In this version, $\tricr(K_5) = \infty$, since crossings have to occur between independent edges (forcing at least $6$ endpoints in a non-planar graph). However, it it easy to give a drawing of $K_5$ with two triple crossings if crossings between adjacent edges are allowed. Another condition that could be relaxed is that independent edges cross at most once.
\complexity Open.
\relations $\cro(G) \leq 3\tricr(G)$\index{crossing number} (perturb triple crossings). The triple crossing number is not monotone (for example, $\tricr(K_{4,4}) = \infty$, while $\tricr(K_{6,4}) = 4$~\cite{TT10}.
\values Tanaka and Teragaito~\cite{TT10} discuss triple crossing numbers of complete and complete bipartite (and $k$-partite) graphs.
\also Degenerate crossing number.
\end{cn}

\entry{Tutte crossing number} See algebraic crossing number.

\begin{cn}{Upward crossing number}\mindex{upward crossing number}
\defn A drawing is {\em monotone} if every vertical line in the plane intersects each edge at most once. The {\em upward crossing number} of a directed acyclic graph $G$ is the smallest number of crossings in a monotone drawing of $G$ in which all edges point in the same direction. We write $\mcro_{\preceq}(G)$, where $\preceq$ is the partial ordering induced by the orientation of $G$. For mixed graphs, containing both directed and undirected edges, the {\em mixed upward crossing number}\mindex{mixed upward crossing number} is the smallest number of crossings in a monotone drawing of $G$ in which all {\em directed} edges point in the same direction.
\reference Based on Eiglsperger, Kaufmann~\cite{EK01}, also Chimani, Zeranski~\cite{CZ14}.
\comments One of the monotone crossing numbers. The upward crossing number corresponds to the layer-free upward crossing minimization problem~\cite{CGMW10}. Eiglsperger and Kaufmann define the notion of a crossing number for a (mixed) upward planarization, calling it the {\em (mixed) upward crossing minimal problem}. Chimani and Zeranski~\cite{CZ14} then use term {\em upward crossing number}. The upward crossing number could also  be called the {\em directed crossing number}\index{directed crossing number} or the {\em hierarchical crossing number}\index{hierarchical crossing number}; the latter term has been used in the context of leveled graphs~\cite{M01}. Generalizing to recurrent hierarchies, one could define a clockwise crossing number (see cyclic level crossing number).
\complexity Even testing whether a graph is {\em upward planar}, that is, has upward crossing number $0$, is \NP-complete~\cite{GT01b}. See~\cite{CZ13} for a survey on upward planarity testing, and~\cite{CZ14} for a survey on exact upward crossing minimization.
\relations $\mcro(G) \leq \mcro_{\preceq}(G)$, where $\preceq$ is the partial ordering induced by the orientation of $G$. The bimodal crossing number is a lower bound on $\mcro_{\preceq}(G)$.
\openq Computing the upward crossing number remains \NP-complete even if we restrict the number of levels at which vertices can be placed: for two levels, the \NP-complete bipartite crossing number\index{bipartite crossing number} is a special case. Is upward planarity fixed-parameter tractable if the parameter is the number of levels?
\also Monotone crossing numbers, bimodal crossing number, bipartite crossing number, clockwise crossing number (under cyclic level crossing number).
\end{cn}

\begin{cn}{Weighted crossing number}\mindex{weighted crossing number}
\defn The {\em weighted crossing number}, $\cro(D,w)$ of a drawing $D$ of a graph $G = (V,E)$ with {\em weights} $w: E^2 \rightarrow \RN_{\geq 0}$, is defined as $\sum_{e,f \in E} w(e,f) \cdot\ i_D(e,f)$, where $i_D(e,f)$ is the number of crossings between $e$ and $f$ in $D$. The {\em weighted crossing number}, $\cro(G,w)$ is the minimum of $\cro(D,w)$ over all drawings of $G$.
\reference Mohar~\cite{M08}, Schaefer, Sedgwick, \v{S}tefankovi\v{c}~\cite{SSS08}.
\comments Assigning weights to edges (as opposed to edge pairs) is an old idea. Integer weights are typically interpreted as parallel copies of simple edges; for many crossing number variants, it is easy to show that $k$ parallel edges correspond to a single edge of weight $k$. This argument may have first occurred in a paper by Kainen~\cite{K72} in which he shows that $\cro_{\Sigma}(G) \leq k^2 \cro_{\Sigma}(G')$ where $G$ is a graph with at most $k$ parallel edges between every pair of vertices, and $G'$ is the underlying simple graph of $G$. If $G$ has exactly $k$ parallel edges between every pair of vertices, then equality holds. This shows, as Scheinerman and Ullman~\cite[Theorem 7.1.4]{SU97} observed, that the {\em fractional crossing number}\index{fractional crossing number} equals the crossing number and thus is of no independent interest. Some crossing number variants, like independent crossing number\index{independent crossing number} and the crossing number of abstract topological graphs\index{crossing number of abstract topological graph}, can be considered special cases of the weighted crossing number. Mohar and Stephen~\cite{MS11} study the expected value of randomly weighted graphs and derives a crossing lemma for this case.
\complexity \NP-complete~\cite{SSS08}.\footnote{This assumes $w$ is considered part of the input (so weights can be large). \NP-hardness follows from Garey, Johnson~\cite{GJ83} since the regular crossing number is a special case. \NP-membership is harder.}
\also Crossing number of abstract topological graph.
\end{cn}

\begin{cn}{Wire crossing number}\mindex{wire crossing number}
\defn A {\em layout} is a partition of a rectangle (the chip area) into two types of smaller rectangles: {\em modules}, where wires end, and {\em regions}, through which wires are routed. Vertices are located on the boundary of modules. An edge between two vertices has associated with it the {\em netlist}, the list of regions it passes through (in the given order) to connect its endpoints. The {\em wire crossing number} is the smallest number of crossings with which all the netlists can be realized.
\reference Based on Groenveld~\cite{G89}. Also, Chen and Lee~\cite{CL98}.
\comments The study of crossings numbers for VLSI layouts goes back to Leighton~\cite{L83}, of course, but after a while more specialzed models developed.\footnote{We should mention that Hotz~\cite[Section 3.6]{H74} develops a notion of (hyperedge) crossing number for circuit layout and poses at least one interesting special problem for the bipartite crossing number. Unfortunately, he works over an abstract notion of circuits introduced using category theory, which makes his text unnecessarily hard to read. His notation for the crossing number of a circuit computing a Boolean function $f$ is $L_V(f)$.} The one described above is closest in spirit to Groenveld's description~\cite{G89} and Chen and Lee's later version~\cite{CL98}. The name {\em wire crossing number} was not used in those papers, but first appears, as far as we know, in~\cite{KGB97}, a paper that describes a slightly different model, and introduces the notion of {\em hypercrossings}\index{hypercrossing}, crossings of hyperedges (Groenveld~\cite{G89} also considers hyperedges, multi-terminal nets in his terminology, but deals with them differently). The wire crossing number as defined above is not particularly interesting as a graph crossing number, because the topology of the edges does not change (with respect to the modules). Any two edges cross at most once, and their isotopy class determines whether they have to cross or not. We decided to include the wire crossing number, since it contains aspects of several other crossing numbers: it is really a special case of the map crossing number\index{map crossing number} or the constrained crossing number\index{constrained crossing number} in which the isotopy type of each edge is fixed. The idea of routing along given tracks (the netlists) is also similar to the Metro-line crossing number\index{Metro-line crossing number}. Marek-Sadowska and Sarrafzadeh~\cite{MS95} also consider what Chen and Lee~\cite{CL98} call the {\em unconstrained} crossing minimization problem in which the isotopy type of the edges is not fixed. Both papers claim a polynomial time algorithm for the problem in this case, which is unlikely, since the unconstrained version of the problem is equivalent to computing a map crossing number, which is \NP-complete~\cite{PSS09d}.\footnote{The two papers really show that one can efficiently find a drawing in which every pair of edges crosses at most once. Such a drawing need not be crossing-minimal, of course.}
\complexity Polynomial time~\cite{G89}.
\relations Map crossing number, constrained crossing number, Metro-line crossing number.
\end{cn}

\entry{$x$-monotone crossing number} See monotone crossing numbers.


\begin{comment}
\begin{cn}{ crossing number}
\defn The {\em  crossing number} of $G$,
\reference
\comments
\complexity
\relations
\values
\openq
\also
\end{cn}
\end{comment}



\section{Some New Questions on Crossing Numbers}

Several open questions have already been embedded in the text above, we don't want to repeat these here. The following questions, as far as we know, are new.

Several authors have studied the parity of crossing numbers of complete graphs, Guy~\cite{G71b}, Kleitman~\cite{K70, K73}, Archdeacon, Richter, and others, but how hard is it to compute?

\begin{question}
  What is the complexity of determining $\cro(G) \bmod 2$?
\end{question}

It's common knowledge that adjacent crossings don't matter, so the following should be easy:

\begin{question}
  Is $\cro(K_n) = \cro_-(K_n)$?\index{independent crossing number}
\end{question}
\begin{comment}
 Is this equivalent to asking whether $\cro(K_n)$ is the same as the crossing number of any subdivision of $K_n$?
\end{comment}

In reality, we do not even know whether there is a good bound on the total number of crossings in a $\cro_-$-minimal drawing of $K_n$. There are many similar open questions for other crossing numbers, for example, $\pcr(K_n) = \cro(K_n)$ \index{pair crossing number}and $\ocr_+(K_n) = \ocr(K_n) = \iocr(K_n)$\index{odd crossing number}\index{odd plus crossing number@odd $+$ crossing number}\index{independent odd crossing number}. For monotone crossing numbers\index{monotone crossing numbers} some progress has been made~\cite{BFK13}.

We know that the $\rcr$\index{rectilinear crossing number} problem is \NPR-complete so, as Bienstock realized, optimal drawings can require exponential precision in the coordinates. What happens if we only have polynomial precision available?

\begin{question}
 Is there a function $f$ so that $G$ has a straight-line grid drawing on a $O(n) \times O(n)$ grid (that is, vertices are grid points) with at most $f(\rcr(G))$ crossings?
\end{question}

We can broaden the question by using the grid crossing number\index{grid crossing number}: is there a function $f$ so that $\gridcr(G,n^k,2) \leq f(\rcr(G))$ for some $k$?

One can also consider games as the source of crossing number definitions; here is a pen and paper crossing game based on an idea from~\cite{MS01}:

\begin{question}
Suppose we arrange $2n$ points on the boundary of a disk; players alternate connecting pairs of points; crossing your own edge costs two points, crossing your opponent's edge costs one point. Who wins?
\end{question}

A recent computer game~\cite{BVRK12} suggests a concrete notion of a game crossing number\index{game crossing number}:
\begin{question}
Two players alternate placing vertices of a graph (a $C_n$ in the original game) for a straight-line drawing of the graph in the plane. A vertex once placed cannot be moved. The first player attempts to minimize the number of crossings, the second player tries to maximize them. What is the largest number of crossings the second player can force in the final drawing?
\end{question}


By Fary's theorem, $\cro(G) = 0$ implies that $\rcr(G) = 0$. Does Fary's theorem generalize to other crossing numbers? For most, it is either an immediate consequence (pair crossing number, local crossing number) or irrelevant (bipartite and book crossing number, for example). The answer is ``no'' for the simultaneous crossing number\index{simultaneous crossing number}, since $\scr(T,P)=0$ for any tree $T$ and path $P$, and there are trees and paths for which $\sgcr(T,P) > 0$~\cite{AGKN12}. What about metric surfaces other than the plane? To take the easiest open example:

\begin{question}
  If a graph can be embedded in a torus, does it always have a geodesic embedding in the torus?\index{geodesic crossing number}
\end{question}

We assume the torus is a standard geometric torus with the natural distance metric inherited from $3$-dimensional space. There is a related result by Mohar~\cite{M99a} for embeddings on surfaces of negative Euler characteristic.

\begin{comment}
Other Fary theorem type question: how hard is it to tell whether $\rcr(G) = \cro(G)$? \NPR-hard? Open for
some families of graph whether equality holds, conjecture for $K_{m,n}$.
\end{comment}

While it's been conjectured that $\pscr(K_n) = \rcr(K_n)$\index{pseudolinear crossing number}\index{rectilinear crossing number}, we do not even know whether the rectilinear crossing number can be bounded in the pseudolinear crossing number.

\begin{question}
  Is there a function $f$ so that $\rcr(G) \leq f(\pscr(G))$ for all graphs $G$?
\end{question}


\subsection*{Acknowledgments}

Thanks to Markus Chimani, Jan Kyn{\v c}l and Gelasio Salazar for corrections and comments, and the anonymous referees for many helpful suggestions.

\begin{comment}
\appendix
\section{Changes}

Since the original version of this survey appeared ( ... )


\end{comment}
\begin{comment}
\appendix
\section{Table of Symbols}

\begin{tabular}{ll}

$K_n$ & complete graph on $n$ vertices
$K_{n,m}$ & complete bipartite graph with partitions of size $n$ and $m$
$C_n$ & cycle of length $n$
$P_n$ & path on $n$ vertices
$W_n$ & wheel graph: single vertex connected to all vertices of a $C_n$
$M_{m,n}$ & $P_m \Box P_n$, the $m \times n$ mesh
$Q_n$ & $\Box_{i=1}^n K_2$, the $n$-dimensional hypercube
$G \Box H$ & Cartesian product of graphs $G$ and $H$
$GP(n,k)$ & Generalized Petersen graph

$\Sigma$ & surface
$\gamma(\Sigma) & genus of surface $\Sigma$
$S_g$ & orientable surface of genus $g$
$N_g$ & non-orientable surface of Euler genus $g$

$\psi$ & generic crossing number
$\psi(e,f)$ & generic crossing number of $e$ and $f$

$X(n)$ &
$Z(n)$ &
$Z(n,m) &

\P\ & polynomial time
\NP\ & non-deterministic polynomial time
\ERP\ & complexity of the existential theory of the reals

\end{tabular}
\end{comment}

\bibliographystyle{plain}
\bibliography{pcr}

\printindex

\end{document}
