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