Graph Crossing Number

Given a "good" graph (i.e., one for which all intersecting graph edgesintersect in a single point and arise from four distinct graph vertices), the crossing number , sometimes also denoted (e.g., Pan and Richter 2007) or , 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 (1983ab) showed that determining the crossing number is an NP-complete problem.

While the graph crossing number allows graph embeddings with arbitrarily-shaped edges (e.g,. curves), the rectilinear crossing number is the minimal possible number of crossings in a straight line drawing of a graph. When the (non-rectilinear) graph crossing number satisfies , (Bienstock and Dean 1993). While Bienstock and Dean don't actually prove the case , they state it can be established analogously to . The result cannot be extended to , since there exist graphs with but for any .

Guy's conjecture suggests that the crossing number for the complete graph is given by , where

(1)

which can be rewritten

$Z(n)={1/(64)n(n-2)^2(n-4) for n even; 1/(64)(n-1)^2(n-3)^2 for n odd.$

(2)

Guy (1972) proved the conjecture for , a result extended to by Pan and Richter (2007). The values of (2) for , 2, ... are then given by 0, 0, 0, 0, 1, 3, 9, 18, 36, 60, 100, 150, 225, 315, 441, 588, ... (OEIS A000241).

It is known that

(3)

(Richter and Thomassen 1997, de Klerk et al. 2007, Pan and Richter 2007).

Richter and Siran (1996) computed the crossing number of the complete bipartite graph on an arbitrary surface.

Zarankiewicz's conjecture asserts that the crossing number for a complete bipartite graph is

(4)

It has been checked up to , and Zarankiewicz has shown that, in general, the formula provides an upper bound to the actual number. The table below gives known results. When the number is not known exactly, the prediction of Zarankiewicz's conjecture is given in parentheses.

	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							81

Kleitman (1970, 1976) computed the exact crossing numbers for all positive .

Graph Crossing Number

Wolfram Web Resources