Computing Beyond Planarity

Die Kreuzungszahl ist die kleinstmögliche Anzahl an paarweisen Kantenkreuzungen wenn man einen gegebenen Graphen in der Ebene zeichnet. Planare Graphen sind jene mit Kreuzungszahl 0. Beyond-Planarity Konzepte beschränken die Zeichnungen bzgl. der erlaubten Kreuzungsstrukturen -- z.B. dürfen Kanten nur beschränkt oft gekreuzt werden, einzelne Kanten dürfen keine zwei nicht-adjazenten Kanten kreuzen, etc. Eine beyond-planare Kreuzungszahl (für ein gegebenes Beyond-Planarity Konzept) ist die kleinste Anzahl an Kreuzungen unter der genannten Einschränkung. Das Maß ist sowohl von theoretischem (toplogische Graphentheorie) als auch praktischen (Graphenzeichnen) Interesse. In diesem Projekt beschäftigen wir uns mit theoretischen und praktischen algorithmischen Methoden zur Bestimmung verschiedener beyond-planarer Kreuzungszahlen: sowohl exakt (mittels ganzzahligen linearen Programmen), als auch heuristisch und approximativ (basierend auf Einfüge- und Planarisierungsmethoden).