Institut für Theoretische Informatik, Algorithmik

GeoNet

Geometrische Netzwerke und ihre Visualisierung


DFG grants WO 758/4-1, 4-2, and 4-3
Gruppenleiter: PD Dr. Alexander Wolff

Projektbeschreibung

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. Die Netzwerke werden als geometrische Graphen repräsentiert, in dem die Objekte (Städte, Personen, etc.) durch Punkte modelliert werden und die Beziehungen selbst (Straßen, Verwandtschaft, etc.) Punkte verbindende Linien oder Streckenzüge sind.

Das Projekt besteht aus zwei Teilen: (a) der Analyse und Konstruktion und (b) der Visualisierung von geometrischen Netzwerken. In Teil (a) liegt der Schwerpunkt auf Netzwerken, in denen der Abstand zweier geometrischer Objekte (zum Beispiel Punkte oder Rechtecke) innerhalb des Netzwerks beschränkt ist durch ein konstantes Vielfaches ihrer Luftlinie (d.h. ihres euklidischen Abstands). Solche Netzwerke heißen euklidische Spanner. Sie haben viele Anwendungen in verteilten Systemen, im Design von Kommunikationsnetzwerken, in der Robotik, der Mustererkennung, der Datenkompression und der Biologie. In Teil (b) geht es um die Frage, wie man geometrische Netzwerke (zum Beispiel U-Bahn-Netze) am besten verzerrt, um sie dann übersichtlich und gut lesbar (etwa als Linienplan) darstellen zu können.

GeoNet ist ein Forschungsprojekt, das die DFG im Rahmen des Aktionsplans Informatik fördert, um Nachwuchswissenschaftlern beim Aufbau ihrer eigenen Arbeitsgruppe zu helfen. Das Projekt hat am 1. April 2003 begonnen und wird maximal fünf Jahre lang finanziert. Die Leitung des Projekts hat Alexander Wolff inne, Doktoranden innerhalb des Projekts sind Marc Benkert, PD Dr. Martin Nöllenburg und Dr. Ignaz Rutter. In der Lehre werden Vorlesungen, Übungen und Seminare im Bereich geometrischer Graphen und Algorithmen durchgeführt sowie Diplomanden betreut.