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

%Changes:




\usepackage{amsmath, amsthm, amssymb,bm}
\usepackage{newtype}
\usepackage{verbatim}
\usepackage[hyphens]{url}
\usepackage[ocgcolorlinks=true,ps2pdf=true,pagebackref=false,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 Change History for \\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{?}{?}\\
\small Mathematics Subject Classifications: 05C62, 68R10}

\begin{document}

\maketitle


\section{Changes Since Original Version }\label{sec:WCN}

Newly added crossing number variants

\begin{itemize}
 \item simple degenerate local crossing number, based on~\cite{E86}
 \item book edge crossing number~\cite{BES13}
 \item monotone odd $+$ crossing number~\cite{BFK13}
 \item crossing number of abstract topological graph~\cite{K91, PPST05, TT07, FPS13}
\end{itemize}

Some bigger changes by topic:

\begin{itemize}
\item Precursors of the crossing number: David Eppstein~\cite{E13} discovered a 1945 paper on crossing minimization in sociology~\cite{B45}, and there is more: \cite{N40, B45, M34, M53, E13,B51}; there now is a remark on ``Forerunners of Crossing Minimization in Sociology''
\item $1$-planarity (a special case of the local crossing number), has been drawing increasing attention recently; newly added results include \cite{CM12, BCE13,FM07,CH13, CK03}
\item some partial progress on Zarankiewicz's conjecture:~\cite{CRS13, DV13}
\item some progress on Guy's conjecture for restricted layouts (monotone, cylindrical, shellable): ~\cite{AAFMRS13a,AAFMRS13b}
\item current best upper bound on $\rcr(K_n)$: \cite{FML14} 
\item results on local rectilinear crossing number:~\cite{D13,S13}
\item results and questions about the relationship between $\cro_{\Sigma}$ and $\cro$: \cite{BPT06, CHS14, PT06a}
\item added Section on crossing lemma variants to introduction (for $\ocr$, $\pcr$, $\pcr_-$, $\iocr$)
\item older papers, I'd so far overlooked: \cite{BK64, B70, W77, E86, M91, SW94, W97,SSSV96a}
\end{itemize}


\section{Detailed Changes}

\begin{itemize}
    \item  added \cite{N40, B45, M34, M53, E13,B51} with a remark on Forerunners of Crossing Minimization in Sociology
    \item added \cite{AAPGCHLRNU13}, drawings in which edges may pass through vertices
    \item added \cite{E13a}, footnote on curve drawing
    \item  added \cite{M99a}, Fary's theorem
    \item  added \cite{C11, CS13}, approximating the crossing number of  bounded degree graphs
    \item  added \cite{CM12, BCE13}, complexity of $1$-planarity
    \item  added \cite{FP13, FP13a}, Metro-line crossing number variant
    \item  added \cite{FM07,CH13}, edge bounds for $1$-planarity
    \item  added \cite{KMNT13}, edge bound for bipartite crossing number
    \item  added \cite{CK03}, coloring $1$-planar graphs
    \item  added \cite{E86}, suggests the (simple) degenerate local crossing number
    \item  added \cite{H74}, crossings in circuit layouts, related to bipartite crossing number
    \item  added \cite{B70}, alternative source for $\rcr(K_8) = 19$.
    \item  added \cite{FDPK13?} on bold drawing style
    \item added \cite{CRS13} on Zarankiewicz's conjecture
    \item added \cite{BK64}, alternative source on upper bound on $\cro(K_n)$
    \item  updated \cite{AAFMRS12} to \cite{AAFMRS13}, updated \cite{dKPS12} to \cite{dKPS13}
    \item  added \cite{L13, W77} on nested convex drawings of $K_n$
    \item  added \cite{W77}, alternative source on $k$-layer crossing number, also added open question to $k$-layer crossing number
    \item  added \cite{BES13}, introduces the book edge crossing number
    \item  added \cite{ABBGHNR13}, results on local convex crossing number
    \item  added \cite{AS13}, a crossing number for geometric hypergraphs; mentioned, not included
    item  added \cite{AAFMRS13a,AAFMRS13b, BFK13}, Guy's conjecture for cylindrical and monotone  layouts
    \item  updated \cite{CM12} to \cite{CM13}
    \item  added \cite{GKT13} introduce new name for local crossing number
    \item  added \cite{FdFRV13, M91}, work on $\bkcr_2(Q_n)$ and $\rcr(Q_n)$   
    \item  added \cite{S13,D13}, results on rectilinear local crossing number
    \item  added \cite{CZ13, CZ14}, upward planarity and upward crossing minimization
    \item  added \cite{SSS13} on $2$-page crossing number of $K_{1,4,n}$
    \item  added \cite{SSvH13}, crossing minimization with port constraints
    \item  added \cite{DV13}, improved bounds for $\cro(K_{7,n})$
    \item  added \cite{A08}, introduces the crossing cover number, not really a crossing number
    \item  added crossing number of abstract topological graph, \cite{K91, PPST05, TT07, FPS13}
    \item  added \cite{SV93}, lower bounds on $\cro_{S_g}(K_n)$, $\cro_{S_g}(K_{n,m})$, and $\cro_{S_g}(Q_n)$
    \item  updated~\cite{DMS13} to \cite{DMS14} 
    \item  added \cite{BPT06, CHS14, PT06a}, relationships between $\cro$ and $\cro_{\Sigma}$
    \item  added \cite{FML14}, improved upper bound on $\rcr(K_n)$
    \item  added \cite{SW94, W97} on relationship between $\rcr$ and Sylvester's Four Point Problem
    \item added \cite{SSSV96a, SSSV96b}, on genus $g$ crossing number
    \item added \cite{HVLS14} on pseudolinear crossing number, sheds some new light on the Bienstock/Dean examples separating $\rcr$ from $\cro$
    
    
\end{itemize}



\bibliographystyle{plain}
\bibliography{pcr}

\printindex

\end{document}
