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
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