Detailseite
Computing Beyond Planarity
Antragsteller
Professor Dr. Markus Chimani
Fachliche Zuordnung
Theoretische Informatik
Förderung
Förderung seit 2026
Projektkennung
Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 574443057
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).
DFG-Verfahren
Sachbeihilfen
