Viele Fragen der rechnerischen und kombinatorischen Geometrie basieren auf endlichen Punktmengen in der euklidschen Ebene. Etliche Probleme aus der Graphentheorie passen ebenfalls in dieses Schema, bei dem Kanten auf gerade Linien beschränkt werden. Eine typische Frage ist das prominente Problem der Rectilinear Crossing Number (das z.B. mit Transportproblemen und der Optimierung von Print-Layouts in Zusammenhang steht): Was ist die kleinste Anzahl von Kreuzungen, die der vollständige Graph von n Punkten aufweist, wenn die Kanten als gerade Linien gezeichnet werden? Dazu gilt die Annahme, daß keine drei Punkte auf einer gemeinsamen Linie liegen.
Es ist leicht zu sehen, daß wir vier Punkte so anordnen können, daß keine Kreuzung von Linien entsteht. Für fünf Punkte zeigt die Abbildung verschiedene Arten, sie anzuordnen. Das sind alles verschiedene Order Types (Goodman und Pollack, 1983). Wenn man fünf Punkte in konvexer Lage anordnet, dann ergeben sich fünf Kreuzungen. Das beste was man tun kann ist, den Graph so anzuordnen, daß man nur eine Kreuzung erhält. Es gibt keinen Weg, den vollständigen Graphen von fünf Punkten ohne Kreuzungen zu zeichnen, auch nicht wenn man Kurven als Kanten erlauben würde. Übrigens, es ist leicht, die Anzahl der Kreuzungen zu maximieren: Man plaziert einfach alle n Punkte auf einem Kreis und erhält so die Maximalanzahl von (n über 4) Kreuzungen.
Die bemerkenswerte Jagd auf Crossing Numbers des vollständigen Graphen wurde in den 60er Jahren von R. Guy eröffnet. Bis zum Jahr 2000 waren nur Werte fuer n<=9 bekannt. Im Jahr 2001 wurde das Problem fuer n=10 geloest und im Jahr 2004 fuer n=11. Das Hauptziel des gegenstaendlichen Projekts ist die Verwendung ausgekluegelter mathematischer Methoden (abstrake Order-Type-Erweiterung), um die Rectilinear Crossing Number fuer kleine Werte von n zu bestimmen. Bis jetzt waren wir erfolgreich für n <= 17. Aus jüngsten (noch nicht einmal veröffentlichten) Forschungsergebnissen weiß man die Rectilinear Crossing Number für n=19 und für n=21. Daher ist das spannendste Problem zur Zeit die Bestimmung des richtigen Wertes für n=18, was das Hauptziel dieses Projekts ist.
Eine ständig aktualisierte Liste der besten heute bekannten Punktmengen kann hier eingesehen werden: http://www.ist.tugraz.at/staff/aichholzer/crossings.html.