Shellable Drawings and the Cylindrical Crossing Number of Kn Article uri icon

abstract

  • The Harary–Hill Conjecture states that the number of crossings in any drawing of the complete graph Kn in the plane is at least (Formula presented.). In this paper, we settle the Harary–Hill conjecture for shellable drawings. We say that a drawing D of Kn is s-shellable if there exist a subset (Formula presented.) of the vertices and a region R of D with the following property: For all (Formula presented.) is the drawing obtained from D by removing (Formula presented.), then vi and vj are on the boundary of the region of Dij that contains R. For (Formula presented.), we prove that the number of crossings of any s-shellable drawing of Kn is at least the long-conjectured value Z(n). Furthermore, we prove that all cylindrical, x-bounded, monotone, and 2-page drawings of Kn are s-shellable for some s≥ n/2 and thus they all have at least Z(n) crossings. The techniques developed provide a unified proof of the Harary–Hill conjecture for these classes of drawings. © 2014, Springer Science%2bBusiness Media New York.

publication date

  • 2014-01-01