Eigenschaften von Bäumen - uni-leipzig.de...Cone Trees [J. Carriere and R. Kazman, “Interacting...

Informationsvisualisierung 4-56

4.4 Bäume

Eigenschaften von Bäumen

Eltern-Kind Relation

Relationen in der Regel gerichtet

Meist mit ausgezeichneten Knoten

Wurzel: keine eingehenden Kanten

Blätter: keine ausgehenden Kanten

Spezielle Algorithmen zum Zeichnen von Bäumen

Optimal bezüglich Kriterien

Optimal bezüglich Zeitbedarf

Informationsvisualisierung 4-57

4.4 Bäume

Beispiele von Bäumen

Organigramm einer Firma

Stammbaum

Taxonomie von biologischen Arten

Phylogenetische Bäume (Evolution)

Software Enginerring

Vererbungsbäume (manchmal auf DAGs)

Syntaxbäume

Informationsvisualisierung 4-58

4.4 Bäume

Darstellungen

Bäume

Gerichtete azyklische Graphen

Graphische Darstellung

Node-Link-Diagramm

Platzfüllendes Diagramm

Kriterien

Platzeffizienz

Abstraktion von Information

Einfachheit

Navigation

Informationsvisualisierung 4-59

4.4 Bäume

Horizontales/Vertikales Layout

Layout Kriterien

Eltern werden über ihren Kindern platziert

Knoten der gleichen Ebene (Abstand zur Wurzel) liegen auf der selben

horizontalen Linie

Reihenfolge der Kinder bleibt erhalten

Symmetrie: der Baum und sein Spiegelbild sollen sich entsprechen

Teilbäume werden mit den gleichen Regeln erstellt

Kleine Teilbäume werden gezielt angeordnet

Symmetrie: Kleine, innere Teilbäume werden gleichmäßig zwischen den großen

Teilbäumen verteilt

Kleine, äußere Bäume sollen nahe den großen Teilbäumen plaziert werden

Schmales, platzsparendes Layout

Informationsvisualisierung 4-60

4.4 Bäume

Walkers Algorithmus [J. Walker. A Node-positioning Algorithm for General Trees. In Software-Practice and

Experience, 20(7). pp. 685-705, 1990.]

Verbesserung, die garantiert lineare Zeit benötigt [Buchheim, C., Jünger, M., and Leipert, S. 2002. Improving Walker’s Algorithm to Run

in Linear Time. In Revised Papers From the 10th international Symposium on Graph

Drawing (August 26 - 28, 2002). S. G. Kobourov and M. T. Goodrich, Eds. Lecture

Notes In Computer Science, vol. 2528. Springer-Verlag, London, 344-353.]

Informationsvisualisierung 4-61

4.4 Bäume

Algorithmus benötigt zwei Druchläufe

Erster Durchlauf

Post-order (links-rechts-Wurzel)

Bestimme vorläufige Positionen

Komplette Teilbäume sind balanciert entsprechend den Layout-

Kritierien

Zweiter Durchlauf

Pre-order (Wurzel-links-rechts, Tiefensuche)

Berechnung der endültigen Positionen

Komplexität: 𝑂(𝑛) 𝑛: Anzahl der KNoten

Informationsvisualisierung 4-62

4.4 Bäume

Beispiel mit k Knoten

[A. Kerren. Animation der semantischen Analyse. Master‘s thesis, Universität des Saarlandes, Saarbrücken, 1997, page 102]

Informationsvisualisierung 4-63

4.4 Bäume

Ausbalancieren der Teilbäume

Ergebnis

[A. Kerren. Animation der semantischen Analyse. Master‘s thesis, Universität des Saarlandes, Saarbrücken, 1997, page 102]

Informationsvisualisierung 4-64

4.4 Bäume

Vorteile der Methode

Knoten der gleichen Ebene sind auf der gleichen horizontalen Ebene

Einfach

Symmetrie

Nachteile (im Allgemeinen)

Hoher Platzbedarf

Große Bäume werden sehr breit

Viel ungenutzte Zeichenfläche

Kein Platz für Bezeichner

Informationsvisualisierung 4-65

4.4 Bäume

Radiales Layout

Konzentrische Kreise

Kinder gleicher Entfernung von der Wurzel liegen auf dem selben Kreis

Prinzipiell gleiche Kritierien wie horizontales Layout

[I. Herman, G. Melancon, M. De Ruiter, and M. Delest. “Latour - A Tree Visualization System”. In Proc. of the Symp. on Graph Drawing, GD’99, pp. 392-399, 1999.]

Informationsvisualisierung 4-66

4.4 Bäume

Bäume können auch H-förmig ausgelegt werden

Wird für Chip-Layout verwendet [P. Eades, „Drawing Free Trees“, Bulletin of the Inst. For the Combinatorics and Its

Applications, pp. 10-36, 1992].

Informationsvisualisierung 4-67

4.4 Bäume

[TUTTLE ET AL: PEDVIS: A STRUCTURED, SPACE-EFFICIENT TECHNIQUE

FOR PEDIGREE VISUALIZATION, InfoVis 2010]

Informationsvisualisierung 4-68

4.4 Bäume

[TUTTLE ET AL: PEDVIS: A STRUCTURED, SPACE-EFFICIENT TECHNIQUE

FOR PEDIGREE VISUALIZATION, InfoVis 2010]

Informationsvisualisierung 4-69

4.4 Bäume

[TUTTLE ET AL: PEDVIS: A STRUCTURED, SPACE-EFFICIENT TECHNIQUE

FOR PEDIGREE VISUALIZATION, InfoVis 2010]

Informationsvisualisierung 4-70

4.4 Bäume

3D

Layout-Algorithmen zum Zeichnen von Bäumen wurden nach

3D portiert

Vorteile

Mehr Platz verfügbar

Selten Schnitte von Kanten

Nachteile

Probleme mit der Navigation

Verdeckungen

Design der Bezeichner

Informationsvisualisierung 4-71

4.4 Bäume

[Herman I; Melancon G; Marshall MS. Graph visualization and navigation in information visualization: A survey. 2000.]

Informationsvisualisierung 4-72

4.4 Bäume

Ansatz von Hong und Eades, 2003 [Seokhee Hong and Peter Eades, Drawing Trees Symmetrically in Three Dimensions, Algorithmica, vol. 36, no. 2,

2003.]

Teilbäume werden auf Teilebenen gezeichnet

Wird eine Partitionierung vorgegeben, so läuft der Algorithmus in linearer

Zeit

Berechnung der besten, balancierten Partitionierung ist NP-hard

[http://www.cs.usyd.edu.au/~shhong/3dtreedraw.htm]

Informationsvisualisierung 4-73

4.4 Bäume

[Seokhee Hong and Peter Eades, Drawing Trees Symmetrically in Three Dimensions,

Algorithmica, vol. 36, no. 2, 2003.]

[http://www.cs.usyd.edu.au/~shhong/3dtreedraw.htm]

Informationsvisualisierung 4-74

4.4 Bäume

[Seokhee Hong and Peter Eades, Drawing Trees Symmetrically in Three Dimensions,

Algorithmica, vol. 36, no. 2, 2003.]

[http://www.cs.usyd.edu.au/~shhong/3dtreedraw.htm]

Informationsvisualisierung 4-75

4.4 Bäume

[Seokhee Hong and Peter Eades, Drawing Trees Symmetrically in Three Dimensions,

Algorithmica, vol. 36, no. 2, 2003.]

[http://www.cs.usyd.edu.au/~shhong/3dtreedraw.htm]

Informationsvisualisierung 4-76

4.4 Bäume

Cone Trees [G. G. Robertson, J. D. Mackinlay, and S. Card, “Cone trees: Animated 3d

visualizations of hierarchical information," in Proceedings of ACM CHI'91, New

Orleans, May 1991, 1991, pp. 189 - 194.]

3D Darstellung von Bäumen

Die Kindknoten sind auf einem Kreis mit Mittelpunkt Elternknoten auf

einer tieferen Ebene angeordnet.

Vorteile

Bessere Ausnutzung des verfügbaren Platzes

Focus & Context

Animation

Nachteile

Knoten verdecken sich

Informationsvisualisierung 4-77

4.4 Bäume

Cone Trees [G. G. Robertson, J. D. Mackinlay, and S. Card, “Cone trees: Animated 3d

visualizations of hierarchical information," in Proceedings of ACM CHI'91, New

Orleans, May 1991, 1991, pp. 189 - 194.]

[C. Chen. Information Visualization. Springer, London, Berlin, Heidelberg, 2nd Edition, ISBN 1-85233-789-3, 2004 , page 308]

[C. Ware. Information Visualization: Perception for Design. 2nd Edition, Morgan Kaufman, San Francisco, ISBN 1-55860-819-2, 2004, page 286]

Informationsvisualisierung 4-78

4.4 Bäume

Cone Trees

[http://www.fask.uni-mainz.de/user/warth/hypertext/diplom/Hypertext-3.5.5.html]

Informationsvisualisierung 4-79

4.4 Bäume

Cone Trees [J. Carriere and R. Kazman, “Interacting with huge hierarchies: Beyond cone trees,“ in Proceedings

of the IEEE Symposium on Information Visualization, (Atlanta, GA), October 1995, 1995, pp. 74-81.]

Informationsvisualisierung 4-80

4.4 Bäume

[C.-S. Jeong and A. Pang, “Reconfigurable disc trees for visualizing large hierarchical information

space," in Proceedings of the 1998 IEEE Symposium on Information Visualization (North Carolina,

October 19 - 20, 1998). INFOVIS. IEEE Computer Society, Washington, DC, 1998, pp. 19-25.]

Informationsvisualisierung 4-81

4.4 Bäume

[C.-S. Jeong and A. Pang, “Reconfigurable disc trees for visualizing large hierarchical information

space," in Proceedings of the 1998 IEEE Symposium on Information Visualization (North Carolina,

October 19 - 20, 1998). INFOVIS. IEEE Computer Society, Washington, DC, 1998, pp. 19-25.]

Informationsvisualisierung 4-82

4.4 Bäume

Degree-of-Interest Trees [Card, S. K. and Nation, D. Degree-of-interest trees: a component of an attention-reactive user

interface. Advanced Visual Interfaces (AVI 2002). 2002, pp. 22-24. Trento, Italy.]

Traditionelle 2D Technik mit folgenden Erweiterungen

Darstellung basiert auf einer Einschätzung des Grades an Interesse

eines Benutzers

Knoten von geringem Interesse werden versteckt

Geometrische Skalierung der Knoten entsprechend dem DOI

Semantischer Zoom

Große, nicht-expandierte Zweige werden geclustert

Animation des Fokuswechsels

Informationsvisualisierung 4-83

4.4 Bäume

Degree-of-Interest Trees

[http://davenation.com/doitree/doitree-avi-2002.htm]

Informationsvisualisierung 4-84

4.4 Bäume

Degree-of-Interest Trees

[http://davenation.com/doitree/doitree-avi-2002.htm]

Informationsvisualisierung 4-85

4.4 Bäume

Botanische Bäume [E. Kleiberg, H. van der Wetering, and J. J. van Wijk. Botanical Visualization of Huge Hierarchies. In

Proceedings of the IEEE Symposium on Information Visualization ‘01, pp. 87-94, 2001.]

Botanische Metapher

Bäume werden als „reale“ Bäume dargestellt

Attribute der Blätter werden auf Farbe und Geometrie

abgebildet

Keine empirische Evaluation

Informationsvisualisierung 4-86

4.4 Bäume

Botanische Bäume

[http://www.win.tue.nl/~vanwijk/botatree.pdf]

Informationsvisualisierung 4-87

4.4 Bäume

Hyperbolische Bäume

Die hyperbolische Ebene ist

eine alternative zur

Euklischen Ebene

Die Fläche eines Kreises

wächst exponentiell mit

seinem Radius

Parallen divergieren

(Kleinsches Modell)

[Ivan Herman, Guy Melançon, and M. Scott Marshall. Graph Visualization and Navigation in Information Visualization: a Survey. 2000.]

Informationsvisualisierung 4-88

4.4 Bäume

Hyperbolische Bäume [John Lamping, Ramana Rao, and

Peter Pirolli, “A Focus+Context

Technique Based on Hyperbolic

Geometry for Visualizing Large

Hierarchies”, Proceedings of the ACM

SIGCHI Conference on Human Factors

in Computing Systems, Denver, May

1995, ACM]

Inspiration: M. C.

Escher „Heaven and

Hell“

Focus & Context,

Fisheye

Animation für

Navigation in Ebenen

Informationsvisualisierung 4-89

4.4 Bäume

Hyperbolische Bäume

Uniform

Tiefe: 5

Verzweigungsfaktor: 3

Informationsvisualisierung 4-90

4.4 Bäume

Hyperbolische Bäume

Fokusänderung

Informationsvisualisierung 4-91

4.4 Bäume