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.<br />
de
dc.description.abstract
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.
en
dc.language
Deutsch
-
dc.language.iso
de
-
dc.rights.uri
http://rightsstatements.org/vocab/InC/1.0/
-
dc.subject
Graphzeichnen
de
dc.subject
Planare Graphen
de
dc.subject
Knadinsky Modell
de
dc.subject
Knickminimierung
de
dc.subject
Graph drawing
en
dc.subject
Planar Graphs
en
dc.subject
Kandinsky Modell
en
dc.subject
Bend Minimization
en
dc.title
Knickminimales orthogonales Zeichnen planarer Graphen im Kandinsky Modell
de
dc.type
Thesis
en
dc.type
Hochschulschrift
de
dc.rights.license
In Copyright
en
dc.rights.license
Urheberrechtsschutz
de
dc.contributor.affiliation
TU Wien, Österreich
-
dc.rights.holder
Canan Yildiz
-
tuw.version
vor
-
tuw.thesisinformation
Technische Universität Wien
-
dc.contributor.assistant
Barth, Wilhelm
-
tuw.publication.orgunit
E186 - Institut für Computergraphik und Algorithmen