Edges with at Most One Crossing in Drawings of the Complete Graph
Heiko Harborth, Ingrid Mengersen · 1990
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 0 (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 0 (n)=2n−2, and estimations of H 1 (n).