(Gerichtete) Graph-Parameter für geometrische Spanngraphen

• Antragstellerin: Dr. Carolin Rehs
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 550144388

Geometrische Graphen sind für viele Anwendungen von großem Interesse: Straßen- und Zug-Netzwerke, Roboterbewegungsplanung, drahtlose Ad-hoc-Netzwerke und viele mehr. Um mit diesen Graphen zu arbeiten und Algorithmen auf ihnen durchzuführen, ist es oft hilfreich die vollständigen Graphen durch kleinere Versionen zu approximieren, insbesondere durch Graphen mit weniger Kanten. Es gibt jedoch wichtige Eigenschaften, die dadurch nicht verändert werden sollten. Insbesondere der Abstand zwischen zwei Punkten im Graph sollte nicht viel größer werden, als ihr Abstand in einem vollständigen euklidischen Graphen. Ein Graph mit dieser Eigenschaft heißt geometrischer Spanngraph. Formal beschrieben, sei P eine Punktmenge in der euklidischen Ebene. Ein geometrischer Spanngraph für P ist ein gewichteter Teilgraph G=(P,E,w) des vollständigen Graphen auf P, wo das Gewicht w(e) einer Kante e der euklidische Abstand zwischen Start- und Endpunkt von e ist. Die Idee hinter geometrischen Spanngraphen ist eine Kantenmenge E zu finden, welche nicht zu groß ist, während der Pfad zwischen zwei Punkten in P nicht zu lang wird. Das wird formalisiert durch den sogenannten Dilatations-Faktor t= max{d((p,p')/|p,p'| mit p,p' Punkte in P }, wobei d(p,p') die Distanz zwischen zwei Punkten in G und |p,p'| der euklidische Abstand zwischen p und p‘ ist. Ein geometrischer Spanngraph mit Dilatation t wird auch t-Spanngraph genannt. In der Algorithmischen Geometrie ist die meist beachtrachtete Eigenschaft eines Spanngraphen – neben der Dilatation – seine Größe. In der Regel wird gefordert, dass geometrische Spanngraphen lineare oder annähernd lineare Kantenanzahl haben, oder die Anzahl der Kanten wird implizit durch andere Eigenschaften begrenzt, zum Beispiel durch Planarität. Weitere Eigenschaften sind das Gesamt-Gewicht oder der maximale Knotengrad. In der Graphentheorie ist ein wichtiges Werkzeug, um effiziente Algorithmen für im Allgemeinen NP-schwere Probleme zu entwerfen, die Eingabe-Graphen durch bestimmte Parameter wie Baumweite und Cliquenweite zu beschränken. In unserer Forschung werden wir geometrische Spanngraphen betrachten, welche durch diese Parameter beschränkt werden, was die Anwendung vieler graphentheoretischer Ergebnisse auf geometrische Probleme und insbesondere effiziente Algorithmen für viele Anwendungen erlaubt.

• DFG-Verfahren: Sachbeihilfen
• Mitverantwortlich: Professor Dr. Kevin Buchin