Given a ``good'' Graph (i.e., one for which all intersecting Edges
intersect in a single point and arise from four distinct Vertices), the crossing number is the
minimum possible number of crossings with which the Graph can be drawn. A
Graph with crossing number 0 is a Planar Graph. Garey and Johnson (1983) showed that
determining the crossing number is an NP-Complete Problem. Guy's Conjecture suggests that the crossing number
for the Complete Graph is
(1) |
(2) |
Order | Predicted | Known |
1 | 0 | 0 |
2 | 0 | 0 |
3 | 0 | 0 |
4 | 0 | 0 |
5 | 1 | 1 |
6 | 3 | 3 |
7 | 9 | 9 |
8 | 18 | 18 |
9 | 36 | 36 |
10 | 60 | 60 |
11 | 100 | |
12 | 150 | |
13 | 225 | |
14 | 315 | |
15 | 441 | |
16 | 588 |
Zarankiewicz's Conjecture asserts that the crossing number for a Complete Bigraph is
(3) |
1 | 2 | 3 | 4 | 5 | 6 | 7 | |
1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | 0 | |
3 | 1 | 2 | 4 | 6 | 9 | ||
4 | 4 | 8 | 12 | 18 | |||
5 | 16 | 24 | 36 | ||||
6 | 36 | 54 | |||||
7 | 77, 79, or (81) |
Consider the crossing number for a rectilinear Graph which may have only straight
Edges, denoted . For a Complete Graph of order , the rectilinear
crossing number is always larger than the general graph crossing number. The first rectilinear crossing numbers for
Complete Graphs are 0, 0, 0, 0, 1, 3, 9, 19, 36, (61 or 62), ... (Sloane's A014540). The
lower limit is from Singer (1986), who proved that
(4) |
(5) |
The first few toroidal crossing number for a Complete Graph are 0, 0, 0, 0, 0, 0, 0, 4, 9, 23, 42, 70, 105, 154, 226, 326, ... (Sloane's A014543). The toroidal crossing numbers for a Complete Bigraph are given in the following table.
1 | 0 | 0 | 0 | 0 | 0 | 0 |
2 | 0 | 0 | 0 | 0 | 0 | |
3 | 0 | 0 | 0 | 0 | ||
4 | 2 | |||||
5 | 5 | 8 | ||||
6 | 12 | |||||
7 |
See also Guy's Conjecture, Zarankiewicz's Conjecture
References
Gardner, M. ``Crossing Numbers.'' Ch. 11 in Knotted Doughnuts and Other Mathematical Entertainments.
New York: W. H. Freeman, pp. 133-144, 1986.
Garey, M. R. and Johnson, D. S. ``Crossing Number is NP-Complete.'' SIAM J. Alg. Discr. Meth.
4, 312-316, 1983.
Guy, R. K. ``Latest Results on Crossing Numbers.'' In Recent Trends in Graph Theory, Proc. New York City Graph Theory Conference,
1st, 1970. (Ed. New York City Graph Theory Conference Staff). New York: Springer-Verlag, 1971.
Guy, R. K. and Jenkyns, T. ``The Toroidal Crossing Number of .''
J. Comb. Th. 6, 235-250, 1969.
Guy, R. K.; Jenkyns, T.; and Schaer, J. ``Toroidal Crossing Number of the Complete Graph.''
J. Comb. Th. 4, 376-390, 1968.
Jensen, H. F. ``An Upper Bound for the Rectilinear Crossing Number of the Complete Graph.''
J. Comb. Th. Ser. B 10, 212-216, 1971.
Kleitman, D. J. ``The Crossing Number of .'' J. Comb. Th. 9, 315-323, 1970.
Singer, D. Unpublished manuscript ``The Rectilinear Crossing Number of Certain Graphs,'' 1971. Quoted in Gardner, M.
Knotted Doughnuts and Other Mathematical Entertainments. New York: W. H. Freeman, 1986.
Sloane, N. J. A.
A014540,
A014543, and
A000241/M2772
in ``An On-Line Version of the Encyclopedia of Integer Sequences.''
http://www.research.att.com/~njas/sequences/eisonline.html.
Tutte, W. T. ``Toward a Theory of Crossing Numbers.'' J. Comb. Th. 8, 45-53, 1970.
© 1996-9 Eric W. Weisstein