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.,
Send comments to dan.archdeacon@uvm.edu
December 2003