DIMACS TR: 98-29

Which Crossing Number Is It Anyway?

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


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