## DIMACS TR: 98-29

## Which Crossing Number Is It Anyway?

### Authors: János Pach and Géza Tóth

**
ABSTRACT
**

A * drawing* of a graph $G$ is a mapping which assigns to
each vertex a point of the plane and to each edge a simple
continuous arc connecting the corresponding two points.
The *crossing number* of $G$ is the minimum number of
crossing points in any drawing of $G$. We define two new
parameters, as follows. The *pairwise crossing number*
(resp. the *odd-crossing number*) of $G$ is the minimum
number of pairs of edges that cross (resp. cross an odd
number of times) over all drawings of $G$. We prove that the
determination of each of these parameters is an NP-complete
problem. We also prove that the largest of these numbers (the
crossing number) cannot exceed twice the square of the
smallest (the odd-crossing number). Our proof is based on
the following generalization of an old result of Hanani,
which is of independent interest. Let $G$ be a graph and let
$E_0$ be a subset of its edges such that there is a drawing
of $G$, in which every edge belonging $E_0$ crosses any other
edge an even number of times. Then $G$ can be redrawn so
that the elements of $E_0$ are not involved in any
crossing.

Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1998/98-29.ps.gz

DIMACS Home Page