Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Graphenzeichnen: Geometrische Aspekte jenseits der Planarität

Fachliche Zuordnung Mathematik
Theoretische Informatik
Förderung Förderung von 2019 bis 2023
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 405764128
 
Erstellungsjahr 2024

Zusammenfassung der Projektergebnisse

Das Ziel unseres Projekts bestand darin, die mathematischen Strukturen besser zu verstehen, die den verschiedenen Möglichkeiten entsprechen, wie man die visuelle Komplexität der Zeichnung eines Graphen messen kann. Beispiele für solche Maße sind die lokale Kreuzungszahl, d. h. die maximale Anzahl von Kreuzungen pro Kante, die Steigungsanzahl, d. h. die Anzahl von verschiedenen Steigungen in einer geradlinigen und kreuzungsfreien Zeichnung, die Streckenzahl oder die Geradenüberdeckungszahl, d. h. die Anzahl von Strecken oder Geraden, die man braucht, um eine geradlinige kreuzungsfreie Zeichnung zu überdecken. Für Graphen werden die Maße als das Minimum über alle Zeichnungen (des entsprechenden Typs) definiert. Ins Zentrum unserer Forschung ist das Maß Streckenzahl gerückt, von dem man schon wusste, dass es NP-schwer zu berechnen ist. Insbesondere konnten wir zeigen, dass es Fest-Parameter-Algorithmen für die Berechnung der Streckenzahl gibt, nämlich bezüglich des natürlichen Parameters, der Geradenüberdeckungszahl und der Knotenüberdeckungszahl. Letzteres war technisch am schwersten zu beweisen. In einer weiteren Arbeit haben wir gezeigt, dass es ETR-vollständig ist, die Streckenzahl zu berechnen, d. h. die Streckenzahl kann einerseits mithilfe der existentiellen Theorie der reellen Zahlen ausgedrückt werden, andererseits ist ihre Berechnung mindestens so schwer wie die Lösung jedes anderen Problems in der Komplexitätsklasse ETR. Außerdem haben wir ein existierendes Resultat bezüglich der Streckenzahl von dreifach-zusammenhängenden kubischen planaren Graphen dahingehend erweitert, dass wir gezeigt haben, dass jeder dreifach-zusammenhängende 4-reguläre planare Graph mit n Knoten eine Streckenzahl von höchstens n + 3 besitzt, was scharf ist bis auf die additive Konstante. Wir haben die ersten universellen unteren Schranken für die Streckenzahl von maximalen Außenpfaden, maximalen außenplanaren Graphen, 2-Bäumen und planaren 3-Bäumen bewiesen. Diese unteren Schranken zeigen, dass existierende Algorithmen für diese Graphklassen konstante Approximationsfaktoren besitzen. Für maximale Außenpfade ist unsere universelle untere Schranke bestmöglich.

Link zum Abschlussbericht

https://oa.tib.eu/renate/handle/123456789/18841

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2026 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung