Article ID Journal Published Year Pages File Type
4652070 Electronic Notes in Discrete Mathematics 2013 4 Pages PDF
Abstract

The Harary-Hill conjecture states that the minimum number of crossings in a drawing of the complete graph Kn is . This conjecture was recently proved for 2-page book drawings of Kn. As an extension of this technique, we prove the conjecture for monotone drawings of Kn, that is, drawings where all vertices have different x-coordinates and the edges are x-monotone curves.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics