Eigenschaften von fast planaren Graphen

• Antragsteller: Professor Dr. Franz Josef Brandenburg
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2019
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 433963685

In der Topologischen Graphentheorie studiert man Graphen, die in der Ebene gezeichnet sind und unterscheidet sie anhand der Struktur von Kreuzungen von Kanten. Bei planaren Graphen sind Kreuzungen verboten. Sie sind die bekannte Graphklasse. Als beyond-planar bezeichnet man Graphen, bei den die Krezungen einer Kante strukturellen Restriktionen genügt. Beispiele sind k-planare Graphen, bei denen jede Kante höchstens k-mal geschnitten werden kann oder fan-crossing Graphen, bei denen die kreuzenden Kanten einen gemeinsamen Endpunkt haben. Bei fan-crossing free ist genau das verboten. Empirische Studien haben gezeigt, dass die Art und die Anzahl der Kreuzungen mit der Lesbarkeit und visuellen Güte von Zeichnungen korrelieren. Wir untersuchen strukturelle Eigenschaften von Klassen von beyond-planar Graphen, und wollen mit neuen Operation Unterscheidungen zwischen verschiedenen beyond-planar Graphklassen herausarbeiten.

• DFG-Verfahren: Sachbeihilfen