
48 CHAPTER 2. CROSSINGS AND PLANARIZATION
In 1983, Leighton used induction on the number of vertices to show the following theorem;
see [Lei83].
Theorem 2.1 Let G = (V, E) be a simple graph. If |E| ≥ 4|V |, we have
cr(G) ≥
1
100
|E|
3
|V |
2
. (2.3)
Ajtai et al. obtained the same result independently with a smaller constant of
1
375
in
[ACNS82]. One of the best-known results has been derived by Pach and T´oth [PT97]. For
any simple graph G = (V, E), cr(G) satisfies
cr(G) ≥
1
33.75
|E|
3
|V |
2
− 0.9|V | . (2.4)
Apart from bounds with respect to the number of vertices and edges, several approaches to
obtain tight lower bounds base d on different graph properties can be