[@ 20040627: 3.3] Welche Verfahren der Informationsvisualisierung eignen sich für die Visualisierung von Graphen? / Welche Verfahren der Informationsvisualisierung wurden speziell dazu geschaffen, Graphen zu visualisieren? ;
Kurzvorstellung der betreffenden Verfahren: Welche Zielsetzungen haben bei der Entwicklung eine Rolle gespielt? ; Wie umfangreich können die Graphen sein (Anzahl der Knoten, Kanten), die durch das jeweilige Verfahren visualisiert werden können?
Recherche-Ergebnisse zu
Informationsvisualisierung,
Visualisierung,
Graph-Visualisierung (Papers, Präsentationen),
interaktive Graph-Visualisierer— Konkret geht es darum, Verfahren vorzustellen, die Graphen visualisieren, etwa den HTV —
"Thinkmap s node-edge display ( Spider )is one of the predefined core configurations. It creates a three-dimensional view that can be rotated to expose more connections. With the Thinkmap Spider,it is possible to view and understand the relationships of thousands of nodes,allowing exploration of dense clusters of information." (Quelle: .../Recherchen / Thes-Vis-Softwares / ThinkMap_(Basis_von_Visual_Thesaurus) / technical_white_paper.pdf; Original
via...; AFAIK liegt Think Map Visual Thesaurus zugrunde.)
"The field of Graph Based Interfaces is still in it's infancy, partially because the main commercial applications such as InXight, TheBrain, and ThinkMap, are proprietary and thus do not allow for outside experimentation and modification of their code." -- TouchGraph, ein Hersteller (
Quelle @ 20040627)
"Early work on automatic graph layout and drawing is scattered through the computer science literature [FPF88,WS79,Moe90]. The first book devoted solely to graph drawing, by Battista and colleagues [BETT99], summarizes large areas of the field. The Graph Drawing conference series beginning in 1994 has resulted in proceedings that cover recent work in both systems and theory. The focus of this thesis is systems, so we do not concentrate on the wealth of theoretical proofs about upper and lower algorithmic bounds: suffice it to say that most interesting computations on general graphs are NP-hard [Bra88]." Munzner,
node7, Abschnitt 2.2 (komplett)
"We present the H3 layout technique for drawing large directed graphs as node-link diagrams in 3D hyperbolic space. We can lay out much larger structures than can be handled using traditional techniques for drawing general graphs because we assume a hierarchical nature of the data. [...] The volume of hyperbolic 3-space increases exponentially, as opposed to the familiar geometric increase of euclidean 3-space. We exploit this exponential amount of room by computing the layout according to the hyperbolic metric. 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. [...] We have successfully laid out hierarchies of over 20,000 nodes." Munzner,
Papers - H3 - Abschnitt "Abstract"Cone Tree-Verfahren (^InfoVis99)
"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)
"Treemap (Bild 7) ist eine Visualisierung von großen, hierarchisch organisierten Informationsmengen, wobei die Hierarchieebenen als ineinander geschachtelte Rechtecke dargestellt werden. Mitte der 90er Jahre wurde diese visuelle Metapher von Ben Shneiderman entwickelt." InfoVis99, S. 8, Abs. 2 (komplett)
"Eine starke Verdichtung des Informationsraums läßt sich durch eine Raumtransformation, z. B. den Übergang vom euklidischen zum hyperbolischen Raum erreichen. Hyperbolic Tree projiziert eine Klassifikationsstruktur, im Beispiel eine Dateiverzeichnisstruktur, auf eine Kugeloberfläche und erlaubt so eine übersichtliche Navigation in relativ großen Informationsstrukturen. In der hyperbolischen Darstellung werden die Baumstrukturen stärker komprimiert als es bei den Kegelbäumen in Bild 4 der Fall ist." InfoVis99, S. 8, Abs. 4
"Walrus is a tool for interactively visualizing large directed graphs in three-dimensional space. By employing a fisheye-like distortion, it provides a display that simultaneously shows local detail and the global context. [...] It is technically possible to display graphs containing a million nodes or more, but visual clutter, occlusion, and other factors can diminish the effectiveness of Walrus as the number of nodes, or the degree of their connectivity, increases. Thus, in practice, Walrus is best suited to visualizing moderately sized graphs that are nearly trees. A graph with a few hundred thousand nodes and only a slightly greater number of links is likely to be comfortable to work with. [...] Walrus uses 3D hyperbolic geometry to display graphs under a fisheye-like distortion. 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. Graphs are rendered inside a sphere that contains the Euclidean projection of 3D hyperbolic space. Points within the sphere are magnified according to their radial distance from the center. Objects near the center are magnified, while those near the boundary are shrunk. The amount of magnification decreases continuously and at an accelerated rate from the center to the boundary, until objects are reduced to zero size at the latter, which represents infinity. By bringing different parts of a graph to the magnified central region, the user can examine every part of the graph in detail."
Walrus @ 20040627
"2.2 Scrolling is Useless
The exponential explosion in size causes overflow off the screen. The general solution of this problem is scrolling. Scrolling is a technique to see, through a window which is physically limited in size, a object which is larger than the window size, by moving it horizontally or vertically. With scrolling, users can see the local details of every part of the tree. <Absatz> In case of huge trees, however, the scrolling is no practical use." http://www.vogue.is.uec.ac.jp/~koike/papers/vl93/vl93.html
für große/riesige Graphen: fraktale Ansätze, selbstähnliche Darstellungen, Pruning//Abschneiden, Fisheye views. http://www.vogue.is.uec.ac.jp/~koike/papers/vl93/vl93.html
http://www.absint.com/aisee/index_de.htm zeigt den Unterschied zwischen hyperbolic tree und fisheye.
Bild
Organigramme, Wireframes, Force Directed Layout, elektrische Schaltungen/Schaltkreise, Flußdiagramme
Bei dieser Gelegenheit bietet sich evtl. an, nach gerichteten und ungerichteten Graphen zu unterscheiden. Mglw. kann dies aber auch bereits in Kapitel 1 erfolgen.
Generell: "In despite of this manifold demand, techniques to visualize such graphs are not common in today's computer applications. So frequently a user has to deal with uncomfortable textual interfaces or poor ad-hoc drawings of graphs, because high-quality graph layout is difficult to implement and reusable tools for graph visualization are often hard to find." (
Quelle [dead link], lokal unter gleichem Namen, Abs. 3 komplett)
Aus
New Developments in Geometric Graph Theory [via CiteSeer], konkret: Dem Inhaltsverzeichnis:
- Proximity Trees
- Tree Drawing
- Planar Straight-Line Upward Drawing
- Planar Graphs
- Lattice Structures
- Triangle Contact Graphs
- (Visualisierung allg.:) Wireframes malen
- Rectangular Duals
- Compact Visibility Representation
- Cone Visibility Graphs
- Automorphism and Genus on Generalized Maps
- Maps
- Triangulations
- Graph Drawings with Smallest Number of Faces
- Layout Twisting
- Topology and Geometry of Planar Triangular Graphs
- Planar Convex Embedding
- PRAM Algorithm
- Planar Maps
- Symmetric Drawings of Graphs
- Unidirected Graphs
- Ranked Digraphs
- Recursive Clusters
- Graph Drawing Algorithms for the Design and Analysis of Telecommunication Networks
- Graph Decomposition
- Planarization
- Planarity Testing
- Connexity of Bipolar Orientations
Mehrzahl der Visualisierungen im Bereich der Informationsvisualisierung sind Baumstrukturen, speziell Dateimanager. Es gibt unzählige visuelle Metaphern, um Baumstrukturen darzustellen: in 2D oder 3D, konzentrisch, hyperbolisch, linear, als Folder, Landschaft oder Karte.
InfoVis99, S. 15, Abs. 1, Satz 1-2
Konkrete Implementierungen für Graph-Zeichner nennt
wiederum Munzner ab dem zweiten Absatz der verlinkten Stelle. - Dies wird auch in den Absätzen nach der darauffolgenden Zwischenüberschrift fortgesetzt.
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. While the fractal tree work was an intriguing beginning and included a 3D view, their system did not tackle the 3D layout problems of ensuring that subtrees do not overlap in space.
Munzner irgendwo, Abs. 2 (komplett)
