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