## 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.

Original language | English |
---|---|

Title of host publication | Proceedings of the 28th Annual Symposuim on Computational Geometry, SCG 2012 |

Pages | 397-403 |

Number of pages | 7 |

DOIs | |

Publication status | Published - 2012 |

Event | 28th Annual Symposuim on Computational Geometry: SCG 2012 - Chapel Hill, United States Duration: 17 Jun 2012 → 20 Jun 2012 |

### Publication series

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

### Conference

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

Country/Territory | United States |

City | Chapel Hill |

Period | 17/06/12 → 20/06/12 |

## Keywords

- Complete graph
- Crossing number
- Topological drawing

## ASJC Scopus subject areas

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint

Dive into the research topics of 'The 2-page crossing number of K_{n}'. Together they form a unique fingerprint.