Alternate Definitions of the Crossing Number



The crossing number of a graph G, cr(G), is the minimum number of crossings over all proper drawings of G. Drawings are assumed to have no crossing of edges with a common endpoint, at most one crossing among nonadjecent edges, and no edge passing through a point.

If we remove the restriction that nonadjacent edges can cross more than once, then we get the pairwise crossing number of G, paircr(G). Here pairs of edges are allowed to cross more than once, but we only count the number of such pairs, not the number of crossings. If we further count only those pairs of edges that cross an odd number of times, we get the odd crossing number, oddcr(G).

It is obvious from the definitions that oddcr(G) is at most paircr(G) which is at most cr(G).

Conjecture: oddcr(G) = paircr(G) = cr(G).

A nice theorem of Chojnacki [C] and Tutte [T] asserts that if a graph can be drawn in the plane so that every pair of edges cross an even number of times, then it is planar. In other words, oddcr(G) = 0 implies cr(G) = 0.

The following weaker conjecture may be more accessible:

Question: Is the ratio cr(G) / oddcr(G) unbounded?

It is known [PT] that cr(GG) is at most 2 oddcr(G)^2.

References:

[C}C. Chojnacki, Uber wesentlich unplattbare kurven im dreidimensionalen raume, Fund. Math. 23 (1935) 135-142.

[PT] J. Pach and G. Toth, Which crossing number is it, anyway?, Proceedings of the 39th Annual Symposium on Foundations of Computer Science, IEEE Press (1998) 617-626. Also in J. of Combin. Theory Ser. B

[T] W.T. Tutte, Toward a theory of crossing numbers, J. of Combin. Theory 8 (1970) 45-53


Submitted by: Dan Archdeacon, Dept. of Math. and Stat., University of Vermont, Burlington, VT 05401-1455 USA

Send comments to dan.archdeacon@uvm.edu

December 2003