Edges with at Most One Crossing in Drawings of the Complete Graph

In 1963 G. Ringel ([3]) determined 2n−2 to be the maximum number of edges without crossings in drawings D(K_n) of the complete graph K_n in the plane. A drawing D(G) is a realization of G in the plane with distinct points (also called vertices) for the vertices of G, and curves (also called edges) for the edges of G such that two edges have at most one point in common, either an endpoint or a crossing. As generalizations it may be asked for the maximum numbers H_s(n) or the minimum num-bers h_s(n) of edges with at most s crossings in drawings D(K_n). In [1] h₀(n) is determined, and h_s(n)=0 for n≧4s+8 holds in general ([2]). Here we will give an alternative proof of Ringel’s result, H₀(n)=2n−2, and estimations of H₁(n).