Four Questions about Drawing the Complete Graph



We ask four questions about drawings of the complete graph K_n in the plane. In a drawing non-adjacent edges are allowed to cross transversally at most once. An empty triangle in a drawing is a K_3 such that all the remaining vertices lie on one side of the triangle.

Question 1: What is the smallest number t(n) of empty triangles in a drawing of K_n?

An upper bound of t(n) at most 2n-4 is known.

The next problem is in the spirit of Ester Klein or of Ramsey. There exists smallest numbers m = Dr(K_n) such that every drawing of K_m contains at least one subdrawing of K_n with the maximum number n(n-1)(n-2)(n-3)/24 of crossings. It is known that Dr(K_5) is at least 11 and at most 113. See [HMS].

Question 2: Does there exist a drawing of K_11 such that every subdrawing of K_5 has only one or three crossings?

Let h(s,n) denote the minimum number of edges with at most s crossings in drawings of K_n. The following question is related to [HT].

Question 3: For which values of n is h(s,n) > 0? Is h(s,n) > 0 for n at most s?

The fourth question arises from [HM].

Question 4: Does there exist a drawing of K_n with the maximum number of crossings such that a) at most one edge is without a crossing, or b) no edge is without a crossing?

Harborth has a drawing of K_n (for each n) with two edges lacking crossings.

References

[HMS] H. Harborth, I. Mengersen, and R.H. Schelp, The drawing Ramsey number Dr(K_n), Australas. J. Combin. 11 (1995) 151-156.

[HT] H. Harborth and C. Thurmann, Minimum number of edges with at most s crossings in drawings of the complete graph, Congressus Numerantium 102 (1994) 83-90.

[HM] H. Harborth and I. Mengersen, Drawings of the complete graph with maximum number of crossings, Congressus Numerantium 88 (1992) 225-228.


Submitted by : Heiko Harborth, Diskrete Mathematik, Technische Universitat Braunschweig, Pockelsstrasse 14, D-38106 Braunschweig, Germany

Send comments to dan.archdeacon@uvm.edu and to h.harborth@tu-bs.de

August, 1995