Aktionsplan-Informatik: Geometrische Netzwerke und ihre Visualisierung

• Antragsteller: Professor Dr. Alexander Wolff
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2003 bis 2011
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5401267

Geometrische Netzwerke sind gewichtete Graphen, deren Knoten Punkten in einem euklidischen Raum entsprechen und deren Kanten mit dem euklidischen Abstand ihrer Endpunkte gewichtet sind. Geometrische Netzwerke sind das Rückgrat bei der Modellierung von Verkehrs-, Waren- und Informationsströmen - ob in der Eisenbahnnetzplanung, dem VLSI-Layout oder der Analyse des Internets. Ich werde unter anderem mit Methoden der algorithmischen Geometrie und Graphentheorie zwei Teilgebiete bearbeiten. Das erste Gebiet ist die Analyse und Konstruktion geometrischer Netzwerke, die Objekte mit gegebener Lage im Raum verbinden und dabei gewisse positive Eigenschaften haben - wie etwa geringen Durchmesser. Von besonderem Interesse sind solche Netzwerke, die einerseits dünn sind, andererseits die Objekte so verbinden, dass der Weg durchs Netzwerk im Vergleich zur "Luftlinie" möglichst nur um einen konstanten Faktor, den Streckfaktor, länger ist. Solche Netzwerke heissen geometrische Spanner, werden angewendet bei verteilten Systemen, Kommunikationsnetzwerken, im VSLI-Design, in der Robotik, in der Mustererkennung, bei der Kompression von Daten sowie in der Biologie und bieten noch viele, interessante offene Fragen. Das zweite Gebiet ist die Visualisierung geometrischer Netzwerke. Da bei solchen Netzwerken die Geometrie schon vorgegeben ist, scheint eines der Hauptprobleme beim Zeichnen von Graphen zu entfallen, nämlich die Knoten des Graphen so in die Ebene einzubetten, dass die resultierende Zeichnung möglichst gut lesbar ist. Das Beispiel U-Bahn-Linienplan zeigt jedoch stellvertretend für viele Arten von technischen Zeichnungen die Schwierigkeit: wie nämlich die zugrunde liegende Geometrie zugunsten einer klareren Darstellung des Netzwerks verzerrt, aber nicht aufgehoben wird. Außer mit Fragen der Modellierung werde ich mich mit Entwurf, Implementierung und experimenteller Analyse von Visualisierungsalgorithmen beschäftigen.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen (Aktionsplan Informatik)