## Abstract

Around 1958, Hill conjectured that the crossing number cr(K _{n}) of the complete graph K _{n} is (equation presented) and provided drawings of K _{n} with exactly Z(n) crossings. Towards the end of the century, substantially different drawings of K _{n} with Z(n) crossings were found. These drawings are 2-page book drawings, that is, drawings where all the vertices are on a line ℓ (the spine) and each edge is fully contained in one of the two half-planes (pages) defined by ℓ. The 2-page crossing number of K _{n}, denoted by ν _{2} (K _{n}), is the minimum number of crossings determined by a 2-page book drawing of K _{n}. Since cr(K _{n}) ≤ ν _{2}(K _{n}) and ν _{2}(K _{n}) ≤ Z(n), a natural step towards Hill's Conjecture is the weaker conjecture ν _{2}(K _{n}) = Z(n), that was popularized by Vrt'o. In this paper we develop a novel and innovative technique to investigate crossings in drawings of K _{n}, and use it to prove that ν _{2}(K _{n}) = Z(n). To this end, we extend the inherent geometric definition of k-edges for finite sets of points in the plane to topological drawings of K _{n}. We also introduce the concept of ≤ ≤ k-edges as a useful generalization of ≤ k-edges. Finally, we extend a powerful theorem that expresses the number of crossings in a rectilinear drawing of K _{n} in terms of its number of k-edges to the topological setting.

Originalsprache | englisch |
---|---|

Titel | Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012 |

Seiten | 397-403 |

Seitenumfang | 7 |

DOIs | |

Publikationsstatus | Veröffentlicht - 2012 |

Veranstaltung | 28th Annual Symposuim on Computational Geometry: SCG 2012 - Chapel Hill, USA / Vereinigte Staaten Dauer: 17 Juni 2012 → 20 Juni 2012 |

### Publikationsreihe

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Konferenz

Konferenz | 28th Annual Symposuim on Computational Geometry |
---|---|

Land/Gebiet | USA / Vereinigte Staaten |

Ort | Chapel Hill |

Zeitraum | 17/06/12 → 20/06/12 |

## Schlagwörter

- Discrete and Computational Geometry

## ASJC Scopus subject areas

- Theoretische Informatik
- Geometrie und Topologie
- Computational Mathematics

## Fingerprint

Untersuchen Sie die Forschungsthemen von „The 2-page crossing number of K_{n}“. Zusammen bilden sie einen einzigartigen Fingerprint.