Graph Visualization (GV) is the study of mathematical graphs and how they can be best visualized for human understanding. Since graphs describe both data and associations between data, graphs have additional information to display compared to other data visualization applications. The key problems to solve in graph visualization are distributing a graph’s nodes and coping with a large graphs with many nodes.Effective distribution of the nodes of a graph has two aims. The first aim is to convey each node’s information and associations in a legible way. Graphs with complicated edges may be unreadable if there are too many lines coming into or out of any node. It is important to structure the graph so that the number of edge crossing are minimized. The second aim is for the graph to be aesthetically pleasing to the reader.
There are many aesthetic metrics including the symmetry of the graph, the number of edge crossings, the relative length of all the edges, the straightness of the lines, and the alignment of the nodes in the graph.
How many tree layouts described in the article? Classify them into three categories by your own way. Give your reasons. (3%) There are 13 tree layouts described in the article. I have classified them into the categories Euclidean, Space Filling and Hyperbolic.
The Euclidean category contains graphs that represents each node in the graph as a point in either 2d or 3d Euclidean space. Edges are represented by lines between each node. This category includes the Traditional Tree, H-tree, Sugiyama Layout, Balloon, Radial and Force Directed layouts. Euclidean layouts can also take advantage of additional layout steps fisheye distortion and zoom and pan.The Space Filling category contains graphs that split a predefined area into sections that represent the nodes.
The size of each section determines the weight of that node. This category contains Treemap graphs, Onion Graphs, Cone Trees and Information Cubes, is the rectangle layout and a 3d example is the Information Cube.The Hyperbolic category contains graphs the represent each node as a point in a hyperbolic plane. Hyperbolic geometry extends traditional Euclidean geometry with a 5th axiom that redefines parallel lines. A Hyperbolic layout is generated in hyperbolic space and then projected onto a 2d or 3d view. The Hyperbolic category include the Hyperbolic Browser and the Klein Model.
After the classification of tree layouts into three approaches, describe the main technical features of each approach accordingly. (2%) EuclideanIn Euclidean layouts the child nodes are positioned in a single direction away from the parent nodes. This direction is typically downwards but could be in any direction or even radiating outwards from a point in concentric circles. For example, Balloon view trees put each level of children in a circle around their parent, with increasingly small circles. The Sugiyama layout is a seminal development in Euclidean layouts that places nodes on a layer depending on their place in the tree’s hierarchy. When an edge spans more than one layer, nodes are moved to new layers. Edge crossing and bends can then be minimized efficiently.Force Directed layout refers to all non deterministic graph layout algorithms. These algorithms run physics like simulations on the nodes to calculate their position. These simulations use Hooke’s law to model modelling using gravitation and magnetic forces.
Different physics models can be used leading to different complexity and different quality of layouts.Space FillingSpace filling layouts begin with single space representing the root node in the tree. Then the space is divided into n spaces, where n is the number of child nodes of the root. The smaller spaces are sized proportional to the weight of each child. This process is repeated until all nodes are represented by a space nested under its parent.
The traditional algorithm to generate a treemap is called slice and dice. It gives alternating vertical and horizontal slices to each node and their children. While this algorithm maintained the order of the tree it resulted in graphs with high average aspect ratio of the spaces. Another algorithm, Squarified, does not maintain the order of it’s child parent relationships, the aspect ratios of the spaces was much closer to 1.This algorithm divides spaces by alternating the orientation of assigned spaces when the aspect ratio of smaller spaces becomes too large.HyperbolicHyperbolic layouts maps the graph onto a hyperbolic curve and then projects it to get the final layout. The root node is placed at the centre of the graph (called the focus) and its children spread outwards. The graph distorts as it approaches the edge because more of the hyperbolic curve is mapped onto the same amount of space on the graph. Nodes near the edge shrink in size and edges are distorted. Poincare and Klein models are two type of hyperbolic projection. The Klein model projects hyperbolic edges as cords on a 2d disk while the Poincare projects hyperbolic edges as arcs.The focus of a hyperbolic layout can be moved away from the root. Regions that move towards the centre of the circle get magnified and their level of focus increases. The opposite is true for regions that move further away from the centre of the circle. When adjusting the focus, node positions in the hyperbolic plane do not need to be changed, the hyperbolic plane is rigidly moved and mapping recalculated. This is true for both Poincare and Klein mapping.
Describe the advantages and disadvantages of these approaches, in terms of efficiency of space utilization, satisfaction of aesthetics rules, computational cost and human cognition process. (3%)EuclideanThe performance of Euclidean layouts is mostly dependant on the performance of edge minimization. General edge crossing minimization has been proven to be an NP problem, even for directed graphs with consecutive layers only. Despite its complexity, minimize edge crossing is a main factor in reducing human cognition load. Euclidean layouts are often efficient at producing graphs that keep to other aesthetics rules such as, grid alignment, total graph area, maximum and average edge length, and symmetryH-Tree and Radial layouts have high performance for rendering binary trees and other well structured trees. However these graphs can be difficult for human cognition as they have an unclear root node that makes the tree more difficult to understand and traverse.
Force Directed layouts are computationally expensive with even the most performant variants taking O(N3) time. Reducing graph size is especially important in Force Directed layouts.
Force Directed layouts can also perform well at edge minimization without additional efforts but do not work for graphs that require frequent or real time updates. Force Directed layouts are non-deterministic and will produce dramatically different outputs with minor or even no changes to the original graph.Space FillingSpace Filling layouts need their spaces to have a low and consistent aspect ratio for the graph to appear aesthetically pleasing and easily understandable. Space Filling layouts are also sensitive to updates of the underlying graph.A single change to the base graph completely changing the treemap. An additional treemap algorithm that was not mentioned in this paper is an Ordered Treemap (Shneiderman and Wattenberg, 2001) that uses a quicksort to create treemaps that have a balance between aspect ratio and smoothness of updates. Update volatility metrics can be measured, such as the layout distance change function and the Hausdorff metric that measure the similarity between two space filling graphs.The Ordered Treemap algorithm is based on quicksort so its complexity is O(n2) worst case and O(n log n) best and average case.
Space filling graphs have 100% space utilization because all the space is designated for the nodes.HyperbolicThe computation performance of hyperbolic layouts is modest on modern systems. A 2 dimensional projection removes need for expensive 3d animation. The Hyperbolic Browser benchmarked 20fps on a 1000 node tree on a desktop PC in 1999. Mapping from Hyperbolic to Euclidean is computationally inexpensive and display complexity is O(log n) up to thousands of nodes, after which it approaches constant.Hyperbolic layouts place a large cognitive load on their users, especially those who are inexperienced. Transformations in Hyperbolic space result in unintuitive rotations and distortions. The Hyperbolic Browser hyperbolic layouts do post-mapping rotation. Post-mapping rotations can maintain the graph’s direction by rotating with respect to the current focus or the root node. Post-mapping rotation can also be used to preserve hierarchy by rotating the graph so the child nodes are always towards the same edge of the screen.Minimum spacing between child nodes is an input to the Hyperbolic Browser that can increase aesthetics. A small angle will allow more nodes to contain more information but each node will have less focus. Vice versa for a larger angle. All 360 degrees of the circle do not have to be used. Decreasing the input angle used by a hyperbolic layout will increase the directionality of the graph.5. How many navigation (reviewing) techniques described in the article? Classify them into categories by your own way. Give your reasons. (1%) There are 4 navigation techniques described in the article. I have classified them into two categories: Focus and Context, and Incremental Exploration.
This essay has been submitted by a student. This is not an example of the work written by our professional essay writers. You can order our professional work here.