Titelaufnahme

Titel
Knickminimales orthogonales Zeichnen planarer Graphen im Kandinsky Modell / Canan Yildiz
VerfasserYildiz, Canan
Begutachter / BegutachterinMutzel, Petra ; Barth, Wilhelm
Erschienen2005
UmfangXV, 156 Bl. : Ill., graph. Darst.
HochschulschriftWien, Techn.Univ., Diss., 2006
Anmerkung
Zsfassung in engl. Sprache
SpracheDeutsch
Bibl. ReferenzOeBB
DokumenttypDissertation
Schlagwörter (DE)Graphzeichnen / Planare Graphen / Knadinsky Modell / Knickminimierung
Schlagwörter (EN)Graph drawing /Planar Graphs / Kandinsky Modell / Bend Minimization
Schlagwörter (GND)Planarer Graph / Orthogonale Darstellung / Knicken / Minimierung / Approximationsalgorithmus
URNurn:nbn:at:at-ubtuw:1-20317 Persistent Identifier (URN)
Zugriffsbeschränkung
 Das Werk ist frei verfügbar
Dateien
Knickminimales orthogonales Zeichnen planarer Graphen im Kandinsky Modell [1.65 mb]
Links
Nachweis
Klassifikation
Zusammenfassung (Deutsch)

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.

Zusammenfassung (Englisch)

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.