Glossar: Graph

[wrs]

Was ist ein Graph?

Ein Graph ist ein Gegenstand, der aus Knoten und Kanten besteht. Die Kanten verbinden entweder zwei verschiedene Knoten miteinander oder einen Knoten mit sich selbst (vgl. u.a. Quelle). Daraus ergibt sich, dass jeder Knoten mit beliebig vielen anderen Knoten verbunden sein kann. Graphen stellen also eine abstrakte Form dar, Strukturen zu beschreiben. Entsprechend werden sie häufig "zur Veranschaulichung von Relationen, insbesondere von Ordnungsrelationen", genutzt (u.a. Quelle).

[/wrs]

"In der Graphentheorie versteht man unter einem Graphen ein Gebilde, das aus Punkten ('Ecken') und Linien ('Kanten') besteht, wobei die Linien zwei verschiedene Punkte oder einen Punkt mit sich selbst verbinden. Graphen dieser Art dienen z.B. zur Veranschaulichung von Relationen, insbesondere von Ordnungsrelationen."

Quelle:
Duden Rechnen und Mathematik, Lektorat des B.-I.-Wissenschaftsverlages unter Leitung von Hermann Engesser. Bearb. von Harald Scheid. – 5. überarb. Aufl. – Mannheim; Leipzig; Wien; Zürich. Dudenverl. 1994. S. 242, Spalte 1


Was ist ein Graph?
http://www-cse.stanford.edu/classes/cs200/Scribes/Tamara_Munzner.html @ 20040416.05:50h MESZ, Abschnitt "Conceptual Background":

Graphs are collections of nodes, and edges (links between nodes). Graphs can be used to represent (...} such complicated networks as the World Wide Web and all of its respective sites and links.

Was verbindet einen Baum mit einem Graphen?
Manche Graphen können Bäume sein - nicht alle Bäume sind Graphen; manche Graphen sind "Beinahe-Bäume": http://www.caida.org/tools/visualization/walrus/ @ 20040416.06:25h MESZ, Abschnitt "Description":

[...] Walrus is best suited to visualizing moderately sized graphs that are nearly trees.

in Stichpunkten beantwortet: Was sind die Kernleistungen der HTVs? / Was sind Stärken?

Was sind die Kern-Leistungen der HTVs? / Was sind Stärken?

Recherche-Ergebnisse zu interaktive Graph-Visualisierern, H3, Graph-Visualisierung (Papers, Präsentationen), Navigation, Kriterien für die Informationsvisualisierung, hyperbolischer Baum, hyperbolische Visualisierung, hyperbolischer vs. Euklidischer Raum, Walrus

The fractal tree work of Koike and Yoshimara [KY93] is similar in spirit to hyperbolic approaches. Both tame the exponential explosion of tree nodes by drawing trees in a mathematical space with nonstandard properties - dimension or distance, respectively.

Munzner irgendwo, Abs. 2, Satz 1-2

Our layout is computed using hyperbolic distances instead of the familiar euclidean distance measure. We use the hyperbolic metric in order to take advantage of the surprising property that hyperbolic space has more room than our familiar euclidean space.

Munzner irgendwo, Abs. 1, Satz 1-2

At any moment, the amount of magnification, and thus the level of visible detail, varies across the display. This allows the user to examine the fine details of a small area while always having a view of the whole graph available as a frame of reference.

Walrus, Abschnitt "Description", Abs. 3, Satz 2-3

We optimize the cone tree layout algorithm for 3D hyperbolic space by placing children on a hemisphere around the cone mouth instead of on its perimeter.

T.Munzner, H3__Laying_Out_Large_Directed_Graphs_in_3D_Hyperbolic_Space.htm, Abschnitt "Abstract", Absatz 1, Satz 3 (via)


Pros & Cons

Hyperbolic trees are very valuable to visualize hierarchical structures such as file directories, web sites, classification hierarchies, organization hierarchies, newsgroup structures, etc. While traditional methods such as paging (divide data into several pages and display one page at a time), zooming, or panning show only part of the information at a certain granularity, hyperbolic trees show detail and context at once.

Quelle, Abschnitt "Pros & Cons"

in Stichpunkten beantwortet: Welche Hyperbolic Tree Views existieren?

Welche Hyperbolic Tree Views existieren? (2D-HTVs, 3D-HTVs; Beispiele für letztere sind Munzners H3, Walrus)

Recherche-Ergebnisse zu interaktive Graph-Visualisierern, H3, Graph-Visualisierung (Papers, Präsentationen)

Hyperbolic Tree der Firma InXight

Im Zusammenhang mit der Entwicklungs von Tools für den Austausch von 3D-Objekten im Web wurden an der University of Minnesota 1994 mit WebViz Nutzeroberflächen vorgestellt, die Informationsstrukturen auf die Oberfläche einer Kugel projezieren, die sogenannten Hyperbolischen Bäume (Hyperbolic Trees). Daraus entwickelten sich in der Folgezeit eine Reihe kommerzieller Nutzeroberflächen für hierarchische Klassifikationsschema wie z.B. der Hyperbolic Tree der Firma InXight.

InfoVis99, S. 5, Abs. 5 (komplett)
Dateimanager MagniFind der Firma Inxight

Bild 8 zeigt den hyperbolischen Dateimanager MagniFind der Firma Inxight,.(Komma + Punkt: sic!) Der entscheidende Vorteil im Vergleich zum Windows-Explorer ist die Möglichkeit einer schnellen, interaktiven Exploration der gesamten Verzeichnisstruktur.

InfoVis99, S. 8, Abs. 1, Satz 4-5

Walrus

Walrus is being developed by Young Hyun at CAIDA. Although Walrus is based on research by Tamara Munzner, she is not connected with this effort in any way, nor does Walrus make use of any code from her H3Viewer.
[...]
Tamara Munzner worked out many of the ideas and techniques underlying Walrus in her Ph.D thesis. [...] Another related work is the hyperbolic tree viewer at Inxight. Walrus differs from their product in at least three ways. We work in 3D instead of 2D, use the Klein model of hyperbolic geometry instead of the Poincare, and use a very different layout algorithm. Laying out graphs in 3D is challenging, as occlusion along the line of sight diminishes some of the benefits of the additional dimension. Hence, 3D layout algorithms can differ considerably from similar 2D algorithms. Walrus uses a modified version of the H3 layout algorithm designed by Munzner."

Walrus, Abschnitt "Description", Abs. 4 komplett; Abschnitt "References", Abs. 1, Satz 1; Abschnitt "References", Abs. 2 (komplett)

H3, Skitter (H3-Abkömmling oder H3 selbst, aber mit untergeschobenen Daten: Measure Forward IP Paths – Measure Round Trip Time – Track Persistent Routing Changes – Visualize Network Connectivity – If you are receiving 52-byte ICMP echo request packets from an IP address belonging to one of our current monitors, they are from skitter (assuming they're not from someone spoofing the source address). We would like sites to be receptive to skitter measurements at low frequency. CAIDA's measurement efforts are intended to help users, providers and researchers understand the complexities in the current and future Internet. skitter research will provide the community with insight into the complexity of a large, heterogeneous, and dynamic worldwide topology.), EBI Hyperbolic Viewer (Java; 5 verschiedene Demos), ...

als Produkt: LexisNexis-Visualisierer; "The webviz system extended cone trees from euclidean to hyperbolic space [MB95]." Munzner irgendwo, Satz 4

als Verfahren: wie bei Walrus angemerkt, solche die auf dem Klein-Modell beruhen und solche, die auf dem Poincare-Modell beruhen. Mglw. gibt es daneben noch weitere.


Noch einmal der Hinweis auf den Unterschied zwischen Fisheye View und HTV: Dort gibt es ein Bild, das den Unterschied auf einen Blick erfassbar macht ("vor Augen führt").

2D hyperbolic tree browser von Xerox PARC; webviz

The first hyperbolic visualization system described in the information visualization literature was the 2D hyperbolic tree browser from Xerox PARC [LR94]. The webviz hyperbolic browser from the Geometry Center [MB95] handled general graphs in 3D. The webviz layout algorithm did not exploit 3D hyperbolic space to its full potential: the amount of displayed information compared to the amount of white space was quite sparse. Moreover, the webviz system drew all links in the graph at all times, so highly connected graphs were quite cluttered.

Munzner irgendwo, Abs. 3 (komplett)


via Info Vis Cyber Infrastructure:

• LexisNexis
• Roget Thesaurus
• International Services Site Map
• Site Manager - Software for Web Publishing and Site Management
• LEXIS-NEXIS Hyperbolic Tree View
• Inxight Tree Studio click on Sitemap
• Deep Green Hyperbolic Trees. Click on Research Tree or Teaching Tree.
• Fern Tree. Try out the different menu options and search!
• Belmont University Hyperbolic Tree
• Go Shopping!