Tóth, Géza


Are different notions of the crossing number the same? ★★★

Author(s): Pach; Tóth

\begin{problem} Does the following equality hold for every graph $G$? \[ \text{pair-cr}(G) = \text{cr}(G) \] \end{problem}

The \Def[crossing number]{Crossing number (graph theory)} $\text{cr}(G)$ of a graph $G$ is the minimum number of edge crossings in any drawing of $G$ in the plane. In the \emph{pairwise crossing number} $\text{pair-cr}(G)$, we minimize the number of pairs of edges that cross. %and the \emph{odd-crossing number} $(\text{odd-cr}(G))$ counts the minimum %number of pairs of edges that cross an odd number of times.

Keywords: crossing number; pair-crossing number

Syndicate content