Title: Knickminimales orthogonales Zeichnen planarer Graphen im Kandinsky Modell
Language: Deutsch
Authors: Yildiz, Canan 
Qualification level: Doctoral
Keywords: Graphzeichnen; Planare Graphen; Knadinsky Modell; Knickminimierung
Graph drawing; Planar Graphs; Kandinsky Modell; Bend Minimization
Advisor: Mutzel, Petra
Assisting Advisor: Barth, Wilhelm 
Issue Date: 2005
Number of Pages: 156
Qualification level: Doctoral
Abstract: 
Graphen werden häufig zur Visualisierung von komplexen Zusammenhängen zwischen verschiedenen Objekten verwendet. Das Gebiet des Graphenzeichnens beschäftigt sich mit dem Problem, automatisch und effizient übersichtliche grafische Darstellungen für Graphen zu konstruieren, sodass die komplexe Struktur der zugrunde liegenden Informationen leicht erfassbar ist. Wir befassen uns mit dem Knickminimierungsproblem in Kandinsky Zeichnungen planarer Graphen, da die Übersichtlichkeit solcher Zeichnungen zum Großteil von der Anzahl der Knicke abhängt. Die Komplexität dieses Problems ist bis heute unbekannt. Wir führen einen neuen 2-Approximationsalgorithmus (Cyclic-Shift Algorithmus) ein der in der Praxis sehr gute Ergebnisse liefert.

Graphs are widely used to visualize complex relations between objects. The field of graph drawing addresses the problem of generating clear drawings for graphs such that the underlying information is easy to conceive. In this work we deal with the problem of minimizing the number of bends in Kandinsky drawings of planar graphs, hence the clearity and readability of such drawings depends mostly on the number of bends. The complexity of this problem is yet unknown. We introduce a new 2-approximation algorithm (Cyclic-Shift algorithm) that yields very good results in praxis.
URI: https://resolver.obvsg.at/urn:nbn:at:at-ubtuw:1-20317
http://hdl.handle.net/20.500.12708/12843
Library ID: AC05031667
Organisation: E186 - Institut für Computergraphik und Algorithmen 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:

Show full item record

Page view(s)

42
checked on Feb 27, 2021

Download(s)

64
checked on Feb 27, 2021

Google ScholarTM

Check


Items in reposiTUm are protected by copyright, with all rights reserved, unless otherwise indicated.