Geometrische Einbettung heterogener Graphen

• Antragsteller: Professor Dr. Thomas Bläsius
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2025
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 562551722

Einbettungen ermöglichen eine einheitliche Repräsentation von Informationen, indem sie hochdimensionale numerische Daten wie Bilder, sowie symbolische Daten wie Text oder Graphen, auf eine niedrigdimensionale numerische Repräsentation abbilden. Das Ziel dieses Projekts besteht darin, effiziente Einbettungsalgorithmen für Graphen zu entwickeln. Das beinhaltet einen Ausbau der theoretischen Grundlagen von geometrischen Graphrepräsentationen, das Studium von komplexitätstheoretischen Fragen, sowie eine sorgfältige Implementierung der entwickelten Algorithmen. Unser Fokus liegt dabei auf heterogenen Graphen, die eine Gradverteilung mit hoher Varianz aufweisen. Solche Graphen stellen in unseren Augen die größten Probleme bei der Berechnung niedrigdimensionaler Einbettungen dar. Die Verwendung von hyperbolischen oder gewichteten Räumen, statt der euklidischen Geometrie, hat das Potenzial dieses Probleme zu beheben, bringt aber auch eigene algorithmische Herausforderungen mit sich, die wir in dem beantragten Projekt angehen werden.

• DFG-Verfahren: Sachbeihilfen