Minimale Anzahl von Kanten mit wenigen Kreuzungen in geradlinigen Darstellungen des vollständigen Graphen
In der vorgelegten Arbeit wird die Frage nach der minimalen Anzahl r_s(n) von Kanten mit jeweils maximal s Kreuzungen in geradlinigen Darstellungen des vollständigen Graphen bearbeitet. Nach einer Einführung in das Thema anhand von verwandten Fragestellungen und deren Ergebnissen wird zunächst die maximale Anzahl von Kreuzungen in geradlinigen Darstellungen, in denen die Anzahl der Knoten auf dem Rand der konvexen Hülle festgelegt ist, nach oben und nach unten abgeschätzt. Für die Kernfrage der Arbeit nach r_s(n) werden obere und untere Schranken sowie exakte Werte für s >= (9/2)n^2 + O(n) angegeben. Ein grundlegendes Ergebnis ist, daß r_s(n) >= 5 für n >= 5 gilt. Es wird gezeigt, daß zu jedem s für n >= (5/3)s^2 + O(s) Darstellungen existieren, deren konvexe Hülle ein Fünfeck ist, so daß nur die Kanten auf dem Rand der konvexen Hülle weniger als s+1 Kreuzungen besitzen. Schließlich werden weitere exakte Werte für kleine n bewiesen. Mit diesen Resultaten und den Abbildungen aus dem Anhang sind für alle s <= 10 und n <= 20 obere Schranken und exakte Werte für r_s(n) angegeben.
This thesis investigates the minimum number r_s(n) of edges with at most s crossings in rectilinear drawings of the complete graph K_n. In the beginning the maximum number of crossings in rectilinear drawings of the complete graph with a fixed number of vertices on the boundary of the convex hull is discussed. For the number r_s(n), lower and upper bounds are given as well as exact values for s >= (9/2)n^2 + O(n). Further, it is shown that r_s(n) >= 5 for n >= 5 and that for every s >= 1 there exists a rectilinear drawing of the K_n with n >= (5/3)s^2 + O(s) such that r_s(n) = 5. For s <= 10 and n <= 20 the values of r_s(n) are either proven or estimated.
Preview
Cite
Access Statistic
Rights
Use and reproduction:
All rights reserved