## 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 P. Erdos and R. 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 M. Simonovits.

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

Title of host publication | Proceedings of the Annual Symposium on Computational Geometry |

Publisher | ACM |

Pages | 124-133 |

Number of pages | 10 |

State | Published - 1999 |

Event | Proceedings of the 1999 15th Annual Symposium on Computational Geometry - Miami Beach, FL, USA Duration: Jun 13 1999 → Jun 16 1999 |

### Other

Other | Proceedings of the 1999 15th Annual Symposium on Computational Geometry |
---|---|

City | Miami Beach, FL, USA |

Period | 6/13/99 → 6/16/99 |

## ASJC Scopus subject areas

- Chemical Health and Safety
- Software
- Safety, Risk, Reliability and Quality
- Geometry and Topology