## Abstract

The crossing number, cr(G), of a graph G is the least number of crossing points in any drawing of G in the plane. Denote by κ(n, e) the minimum of cr(G) taken over all graphs with n vertices and at least e edges. We prove a conjecture of Erdos and Guy by showing that κ(n, e)n^{2}/e^{3} tends to a positive constant as n → ∞ and n ≪ e ≪ n^{2}. Similar results hold for graph drawings on any other surface of fixed genus. We prove better bounds for graphs satisfying some monotone properties. In particular, we show that if G is a graph with n vertices and e ≥ 4n edges, which does not contain a cycle of length four (resp. six), then its crossing number is at least ce^{4}/n^{3} (resp. ce^{5}/n^{4}), where c > 0 is a suitable constant. These results cannot be improved, apart from the value of the constant. This settles a question of Simonovits.

Original language | English (US) |
---|---|

Pages (from-to) | 623-644 |

Number of pages | 22 |

Journal | Discrete and Computational Geometry |

Volume | 24 |

Issue number | 4 |

DOIs | |

State | Published - Dec 2000 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics