Mahmoud Kassem

Über das planare Morphing zwischen Zeichnungen planarer Graphen

Betreuer: Frank Hoffmann
Abschluss: Bachelor of Science (B.Sc.)
Abgabedatum: 27.02.2015

Kurzbeschreibung

Ein planares Morphing ist eine stetige Transformation zwischen topologisch äquivalenten straight-line-Zeichnungen Z_s und Z_t desselben planaren Graphen G. Ein solches Morphing kann z.B durch eine Sequenz von linearen Morphingschritten angegeben werden, dabei bewegt sich jeder Knoten in jedem Schritt mit konstanter Geschwindigkeit auf einer Geraden und zu jedem Zeitpunkt liegt eine topologisch äquivalente Zeichnung vor. Die Komplexität des Morphings ist dabei die Länge dieser Sequenz, also die Anzahl der linearen Morphingschritte. In einer Arbeit aus dem Jahre 2014 haben Angelini et al. gezeigt, dass für einen gegebenen planaren Graphen G und topologisch äquivalenten straight-line-Zeichnungen Z_s und Z_t eine Morphingsequenz existiert, deren Länge in O(n) liegt, wobei n die Anzahl der Knoten des Graphen ist. Auf der anderen Seite existieren Zeichnungen ein und desselben planaren Graphen auf n Knoten, sodass jede lineare Morphingsequenz Ω(n) Schritte benötigt. Die Bachelorarbeit entwickelt zunächst die Grundlagen und präsentiert dann die wesentlichen Ideen der Arbeit.