Institut für Theoretische Informatik, Algorithmik

Generalisierung von geometrischen Graphen

Diplomarbeit

Bei vielen Graphen hat man neben der Nachbarschaftsrelation der Knoten zusätzliche geometrische Informationen, etwa Koordinaten für die Knoten und Kurven für die Repräsentation der Kanten. Diese Informationen können entweder über einen Zeichenalgorithmus gewonnen werden oder, wie im Falle von Straßengraphen, inhärent zum Graphen gehören.

Versucht man nun sich mit Hilfe einer Zeichnung einen Überblick über den Graphen zu verschaffen, so stößt man auf das Problem, dass beim Herauszoomen der Graph „verschlammt“: Nahe beieinander liegende Knoten können visuell nicht mehr getrennt werden und ganze Mengen von Kanten verschmelzen zu einer Fläche. Zudem verursachen detailreiche Kantenzüge auch dann noch Aufwand beim Zeichnen, wenn sie schon längst nicht mehr optisch auflösbar sind.

Daher ist man daran interessiert, den Graphen für eine gegebene Zoomstufe so zu vereinfachen, dass seine Grobstruktur besser sichtbar wird. Diese Vereinfachung heißt auch Generalisierung. Hierzu können etwa nahe beieinander liegende Knoten miteinander identifiziert werden und weniger wichtige Kanten entfernt werden. Im Rahmen dieser Arbeit soll zunächst die Generalisierung geometrischer (d.h. geradlinig gezeichneter) Graphen untersucht werden.

Straßennetz von Europa in unterschiedlichen Detailgraden

Europa
Südwest-Deutschland
Karlsruhe

Kurzbeschreibung

Art

Diplomarbeit

Ziele

Ziel der Arbeit ist der Entwurf von Algorithmen zur automatischen Generalisierung von geometrischen Graphen. Die Generalisierungen sollen dabei die Grobstruktur des Ausgangsgraphen möglichst gut wiedergeben.

Vorraussetzung

fundierte algorithmische Kenntnisse

Kontakt