7.3. Crossing Number
If a graph G is not planar then we can draw the
graph in such a way that some edges crossin each other. The crossing number of a graph G is the minimum number of
crossing of its edges among the drawings of G in the plane. It is
denoted by .
While we drawing a graph we assume that
- adjacent edges never cross
- two nonadjacent edges cross at most once
- no edge crosses itself
- no more than two edges cross at a point of the plane
Some easy observations :
- a graph G is planar iff .
- If then
.
- If H is a subdivision of G
then
Theorem 7.11. (Guy, 1960): For complete graphs,
and equality holds if .
Turán's Brick-Factory Problem: There were some kilns where the bricks were made, and some open storage yards were the bricks were stored. All the kilns were connected by rail with all the storage yards, and the bricks were carried on small wheeled trucks to the storage yards.
The trouble was at the crossing: the trucks generally jumped the rails there, and the bricks fell out of them.
The loss of time could have been minimized if the number of crossing of the rails had been minimized.
Turán realized that the actual situation could have been improved, but the general problem with s kilns and t storage yards seemed to be very difficult.
Conjecture 7.12. (Zarankiewicz-conjecture):
The conjecture was investigated by Kleitman in 1970. He
proved that the conjecture is true if s and t are integers and either
or
and
. From this it follows that
.