The crossing number
\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}${\mbox{\sc cr}}(G)$\end{document}
of a graph G is the minimum possible number of edge-crossings in a drawing of G, the pair-crossing number
\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}${\mbox{\sc pair-cr}}(G)$\end{document}
is the minimum possible number of crossing pairs of edges in a drawing of G, and the odd-crossing number
\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}${\mbox{\sc odd-cr}}(G)$\end{document}
is the minimum number of pairs of edges that cross an odd number of times. Clearly,
\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}${\mbox{\sc odd-cr}}(G)\le {\mbox{\sc pair-cr}}(G)\le {\mbox{\sc cr}}(G)$\end{document}
. We construct graphs with
\documentclass[12pt]{minimal}
\usepackage{amsmath}
\usepackage{wasysym}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsbsy}
\usepackage{mathrsfs}
\usepackage{upgreek}
\setlength{\oddsidemargin}{-69pt}
\begin{document}$0.855\cdot {\mbox{\sc pair-cr}}(G)\ge {\mbox{\sc odd-cr}}(G)$\end{document}
. This improves the bound of Pelsmajer, Schaefer and Štefankovič. Our construction also answers an old question of Tutte.
