Bibliographic Metadata

Title
Knickminimales orthogonales Zeichnen planarer Graphen im Kandinsky Modell / Canan Yildiz
AuthorYildiz, Canan
CensorMutzel, Petra ; Barth, Wilhelm
Published2005
DescriptionXV, 156 Bl. : Ill., graph. Darst.
Institutional NoteWien, Techn.Univ., Diss., 2006
Annotation
Zsfassung in engl. Sprache
LanguageGerman
Bibl. ReferenceOeBB
Document typeDissertation (PhD)
Keywords (DE)Graphzeichnen / Planare Graphen / Knadinsky Modell / Knickminimierung
Keywords (EN)Graph drawing /Planar Graphs / Kandinsky Modell / Bend Minimization
Keywords (GND)Planarer Graph / Orthogonale Darstellung / Knicken / Minimierung / Approximationsalgorithmus
URNurn:nbn:at:at-ubtuw:1-20317 Persistent Identifier (URN)
Restriction-Information
 The work is publicly available
Files
Knickminimales orthogonales Zeichnen planarer Graphen im Kandinsky Modell [1.65 mb]
Links
Reference
Classification
Abstract (German)

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.

Abstract (English)

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.