T Von Landesberger

A Kuijper

T Schreck

J Kohlhammer

J J Van Wijk

J.-D Fekete

D W Fellner

Visual Analysis of Large Graphs: State-of-the-Art and Future Research Challenges

Keywords: (according to ACM CCS): Data Structures [E, 1]: Graphs and Networks; Trees-Mathematics of Computing [G, 2, 2]: Discrete Mathematics-Graph Theory Information Systems [H, 4]: Applications-Information Systems [H, 5, 2]: Interfaces and Presentation-User Interfaces

The analysis of large graphs plays a prominent role in various fields of research and is relevant in many important application areas. Effective visual analysis of graphs requires appropriate visual presentations in combination with respective user interaction facilities and algorithmic graph analysis methods. How to design appropriate graph analysis systems depends on many factors, including the type of graph describing the data, the analytical task at hand, and the applicability of graph analysis methods. The most recent surveys of graph visualization and navigation techniques cover techniques that had been introduced until 2000 or concentrate only on graph layouts published until 2002. Recently, new techniques have been developed covering a broader range of graph types, such as time-varying graphs. Also, in accordance with ever growing amounts of graph-structured data becoming available, the inclusion of algorithmic graph analysis and interaction techniques becomes increasingly important.

In this State-of-the-Art Report, we survey available techniques for the visual analysis of large graphs. Our review firstly considers graph visualization techniques according to the type of graphs supported. The visualization techniques form the basis for the presentation of interaction approaches suitable for visual graph exploration. As an important component of visual graph analysis, we discuss various graph algorithmic aspects useful for the different stages of the visual graph analysis process. We also present main open research challenges in this field.

Introduction

The analysis of graphs is important in many application areas including finance, biology, sociology, transportation, and software engineering; It includes a variety of different tasks. The main aspects relate to the understanding of global and local structure of the graph, the connections between entities, the clusters of highly connected entities, etc. Such high level tasks often consist of a series of low level tasks [LPS * 06], in particular when dealing with large and complex graphs.

The analysis of graphs is often supported by their visual presentations. In this respect, graph visualization research concentrates on the development of effective graph layouts and visual mappings. The visualization of large graphs is accompanied by effective interaction techniques, in particular, in cases when the whole graph is too complex or large to be visualized in one static view. The interaction alone may not be sufficient to accomplish certain analytical tasks. Therefore, algorithmic support -such as machine learning, or graph analysis algorithms -needs to be supported in interactive visualization systems. Such integrated visual analysis of large data sets is the main focus of the research field called Visual Analytics, which evolved from Information Visualization and Scientific Visualization [KMS * 08]. It has effectively started to grow after the publication of the seminal Our motivation for this report is two-fold. First, we recognize that by now most recent graph visualization survey [HMM00, DPS02] date back several years. Therefore, we aim to provide an update by adding more recent publications to the body of work presented in these surveys. Second, we aim to take a Visual Analytics perspective on the field of visual graph analysis by explicitly considering in a unified way the aspects of visual representation, user interaction, and algorithmic analysis (see Figure 1). These three elements form the basis for effective visual graph analysis systems and are closely interrelated. For example, algorithmic graph analysis may be applied as a preprocessing step before a specific graph layout is determined for visual representation. Interactive direct object manipulation approaches are often useful for exploring large and complex graphs visually. Also, by means of user interaction, further graph analytic processing steps, or updates to the presented views, can be requested. The algorithmic analysis thereby helps to reveal interesting aspects of the data. The user involvement in this analytic process can vary from an automatic analysis, where the calculation is done without user involvement, over a user-driven analysis, where the user triggers the algorithmic processing of the data, up to a user-steered process where the user has full control over the analytical process including setting the algorithm parameters.

In this state-of-the-art report, we provide a systematic overview of the main approaches in each of the three aspects of visual analysis of graphs. We therefore develop a classification of techniques according to these aspects. Within each category, we refer to exemplary papers, while focusing on new developments in the visual graph analysis area. We discuss the respective techniques, in order to offer the reader the possibility to concentrate on methodological aspects of visual analysis of graphs applicable across various domains. Owing to the broad scope of the article, we present the main features (strengths and weaknesses) of the techniques as far as they were discussed by the authors of the papers or were mentioned in evaluations. In particular cases, we point out the readers to evaluation papers for more details. The structure of the report reflects the steps of the visual analytics process introduced by Keim et al. [KAF * 08] (see Figure 2). Section 2 details on definitions and a classification of graphs by types and introduces main pre-processing methods for visual graph analysis. This section is the basis for a discussion of visual graph representations given in Section 3. Sections 4 and 5 survey key approaches for interaction with and algorithmic analysis of graphs in visualization, respectively. Finally, Section 6 concludes and outlines future challenges in this research domain.

Basic Graph Definition and Preprocessing Techniques

In this section, we recall fundamental graph definitions as well as approaches for graph preprocessing useful for subsequent graph visualization.

Definitions

Graphs are a prominent data structure within Visual Analytics and related research fields. Often, graphs are applied for describing relationships between entities. A graph refers to a set of vertices (nodes) and a set of edges (i.e., links) that connect pairs of vertices. It is a pair

G = (V, E); E ⊆ [V 2 ],
where elements of V are vertices and elements of E are edges [START_REF] Diestel R | Graph Theory[END_REF]. Furthermore, attributes can be attached to vertices and edges, e.g., to denote their type, size, or some other application related information.

submitted to COMPUTER GRAPHICS Forum (1/2011).

Graphs are often classified into undirected and directed [HMM00]. For a directed graph (resp. undirected), the edge vertices e = (v 1 , v 2 ) are ordered (resp. unordered). A graph containing both directed and undirected edges is called mixed.

A path of length s in G is a sequence of connected vertices path G (a 1 , as) = a 1 , a 2 , . . . , as where a i ∈ V and (a i , a i+1 ) ∈ E. A cycle is a closed path with a 1 = as. A tree is a connected undirected graph without cycles [START_REF] Diestel R | Graph Theory[END_REF]. A Tree T is called rooted when one vertex r is distinguished as a so called root node: T = (V, E, r). Such trees are often treated as hierarchies, where the length of the path to the root denotes the level of a vertex in the hierarchy. However, formally, a hierarchy is a directed acyclic graph so, in a formal hierarchy, a node can have several paths to the root node. In this survey, we use the the term hierarchy as synonym to "rooted tree". Note that a connected graph can be transformed to a tree by removing edges causing cycles while keeping the graph connected.

In graph theory literature, a directed graph with weighted edges is also called a network. In information visualization, the term network is often used in a broader sense denoting a graph with attributes associated with vertices and edges.

An additional graph category are so-called compound graphs. A compound graph C = (G, T ) is defined as a graph G = (V, E G ) and a rooted tree T = (V, E T , r) that share the same set of vertices, such as:

∀e = (v 1 , v 2 ) ∈ E G , v 1 ∈ path T (r, v 2 )andv 2 ∈ path T (r, v 1 )
Relationships between vertices are expressed by T : vertices sharing a common parent in T belong to the same "group". When two vertices sharing a common parent are connected in G, they share a generic relationship. Many other kinds of relationships can be expressed including hierarchic and cross-group.

Compound graphs can be created by successive aggregation (or clustering) of graph vertices in a bottom-up approach. This operation usually involves creating new nodes as group/cluster parents. In this case, vertices (and implicitly, also edges) of the original graph are aggregated (i.e., added as children of the group parent), thereby creating constructed meta-nodes or super-nodes. The attributes of the meta-nodes can be calculated from the attributes of the merged nodes. Similarly, edges between meta-nodes are aggregated into meta-edges and their attributes can be calculated from the original edges. Compound graphs which are constructed in this way are also referred to as aggregated graphs. The list of operations that can be performed on such graphs is dependent on the particular application and graph type. Graphs may also evolve over time, thereby forming dynamic graphs (i.e., time-dependent graphs) in contrast to static graphs. Time-dependent changes may affect the attributes of nodes and edges, the graph structure, or both. Furthermore, graphs may be distinguished according to their topological properties. There exists a variety of literature on graph theory (e.g., [START_REF] Diestel R | Graph Theory[END_REF]) which focuses on graph terminology, classification, and algorithmic graph analysis. In the following, we mention only the most relevant terminology used later in this report. Basic graph properties include the number of nodes, graph density, and connectivity. Properties are often taken into account (or are a prerequisite) for certain visualization techniques. These properties often heavily influence which visualization methods can be used or fall short, with respect to readability and performance. For example, the increasing number of nodes, higher graph density, or both pose a scalability problem in visualization owing to limited display space and human perception capabilities. According to the graph size, graphs are often referred to, e.g., as small or large. The definition of large graphs is however not standardized. Often graphs with thousands, hundreds of thousands or millions of nodes are called large. However, not only the number of nodes determines the notion of a "large" graph. Graph density and connectivity also play an important role for the notion of a "large" graph. From the visualization point of view, "large" graphs usually lead to cluttered displays. In algorithmic analysis, "large" graphs refer to long computational times or memory footprint larger than the available RAM size. A discussion about the influence of graph size and density on visualization and construction of graphs for testing visualizations according to these parameters is provided in [Mel06].

Several special graph structures appear often in realsubmitted to COMPUTER GRAPHICS Forum (1/2011). world cases, and dedicated visualization methods have been developed for these [ACJM03,vHW08,JHGH08,MJW * 09]. For example, social networks usually exhibit a structure called small world network: the typical distance between two nodes grows proportionally to log |V |. Scale-free networks, e.g., protein networks or certain types of social networks have a degree distribution that follow approximately the power law. Bipartite graphs are graphs whose nodes form two disjoint sets:

V 1 ,V 2 with V 1 ∪ V 2 = V and V 1 ∩ V 2 = ∅, such that: ∀e = (v 1 , v 2 ) ∈ E, v 1 ∈ V 1 andv 2 ∈ V 2 .

Algorithmic Graph Preprocessing

In graph visualization, algorithmic graph preprocessing often includes graph simplification to reduce the size, while maintaining the main graph structure. Also pre-processing of graph properties can be used for graph visualization (in algorithms for positioning of nodes and edges) or highlighting of interesting parts of the graph. The modified graph is used then for an easier visual inspection as large and complex graphs are difficult to understand even using advanced node and edge positioning algorithms (layouts). Such preprocessing steps can usually be performed automatically without user interaction. There are two main approaches to graph reduction: graph filtering and graph aggregation.

Graph filtering There are two types of filtering: stochastic and deterministic. Stochastic filtering is mainly based on random selection of nodes and edges from the original graph. These methods are compared in [LF06]. Deterministic filtering uses, as its name suggests, a deterministic algorithm for the selection of the nodes/edges to be removed. This filtering can be based on node/edge attributes, on topologic values such as betweenness centrality, or other graph properties. For example, filtering based on edge-betweenness-centrality can be used for removal of less important edges while keeping the underlying structure (connectedness and other features such as cliques) of the graph [START_REF] Jia | On the visualization of social and other scale-free networks[END_REF] (see Figure 4).

Graph aggregation

In this approach, nodes and edges are merged to single nodes and edges, thereby reducing the size of the graph and revealing relationships between groups of nodes. Graph aggregation can be repeated multiple times, creating a hierarchical graph, which is a special kind of compound graph. There are various ways of aggregating a graph, including using predefined node hierarchies, or aggregation according to node attributes, or according to the node clusters [EDG * 08, BDL * 10], to name a few. Figure 5 (top) shows an example aggregation schema with several aggregation levels. The highlighted rectangle shows the corresponding data in each aggregation level. Figure 5 (bottom) shows the original and aggregated data in a matrix visualization.

Visual Representations of Graphs

Visualization is one of the main means of exploratory graph analysis. It includes the development of appropriate types of visual representations (e.g., matrix or node-link diagrams), efficient placement of graph elements on the screen and efsubmitted to COMPUTER GRAPHICS Forum (1/2011).

ficient visual attribute mappings (design of graph elements for improved readability of the drawing).

In computer-created graph visualization, several so-called aesthetic criteria are taken into consideration. They are usually implemented as objective functions to optimize in layout algorithms. The standard criteria include minimizing the number of crossings, minimizing the total drawing area, maximizing symmetries and many more related to particular types of graphs and edge drawing styles [Pur97, DBETT99, BBD09]. Recently, Beck et al. [START_REF] Bennett | The aesthetics of graph visualization[END_REF] extended previous works to focus on both static and dynamic graphs irrespective of their graphic representations (including also matrix representations in addition to node-link diagrams). They consider three groups of criteria: general, dynamic and aesthetic scalability.

• The general criteria include reduction of visual clutter, reduction of spatial misunderstanding resulting from spatial closeness, maximization of spatial matching of items for following paths and maximization of space efficiency. • For dynamic graphs, the following criteria are desired: maximization of display stability between time points, reduction of cognitive load when analyzing time dynamics, minimization of temporal aliases mainly owing to positioning of different nodes in the same place in two time periods.

• Aesthetic scalability criteria refer to graph readability for larger graphs, i.e., scalability in number of vertices (i.e, increasing graph order), scalability in number of edges (i.e., increasing graph density), and scalability in number of graphs, in particular with increasing number of time steps for which graph data is given.

All these criteria are important but they cannot be simultaneously optimized and are not sufficient to design a good layout which is usually data and task dependent. Therefore, exploratory graph visualization requires more than one layout algorithm to reveal the several perspectives on relationships between nodes.

In this section, we describe the main graph visualization techniques following the graph classification from Section 2. We introduce techniques for static and time-varying graphs. In each part, techniques for hierarchies, generic directed and undirected graphs, and compound graphs are presented. We discuss different ways of visual graph representations and designs of graph drawings.

Visual Representations of Static Graphs

The visualization of static graphs has received much attention in the Information Visualization community. The section start with trees that are simpler than general graphs.

Trees

Techniques for displaying trees can be divided into three main groups: Space filling, node-link based, and hybrid (see Figure 6). There have been several studies comparing the different ways of visualizing trees [SCGM00, BN01, vHvW02, Kob04, AK07]. A very useful visual overview of tree visualization has been provided in the poster [JS10]. It is difficult to unify these results as they differ significantly. Recently, Ziemkiewicz and Kosara have shown that the effectiveness of the visualization technique depends not only on the task to be solved, but also on the formulation of the task assignment, i.e., if it reflects a containment or a level metaphor [START_REF] Ziemkiewicz | The shaping of information by visual metaphors[END_REF]. or hyperbolic layouts [LRP95,Mun97,AH98] (see Figure 7). Most of these classic tree layout algorithms have a linear complexity in time and memory so the layout computation is scalable. However, the node-link representation by design leaves significant background space empty and thereby may encounter scalability problems when applied to larger graphs. For the visualization of node attributes, specialized techniques for multi-dimensional data visualization such as glyphs, radial or parallel plots have been used.

Space filling techniques These techniques try to use the full area of the display to present the hierarchy. Instead of employing links for representing node relationships, the spatial positions of nodes are employed, using either closeness or enclosure. They are mainly applied to visualization of hierarchic partitions of sets of data items, for instance files in a file system. Area size can be used to encode quantitative attributes of nodes, such as file size. Additionally, color and height can represent additional data attributes. In case more complex additional information needs to be displayed, specialized data presentations can be placed in the child nodes such as icons, parallel coordinate diagrams, etc. Space-filling techniques can be categorized by the placement strategy employed into enclosure, adjacency and crossing (see Figure 8). or on linear layers, yielding so-called icicle plots. The advantage of this visualization is that the parent nodes are not overlapped by their child nodes and therefore, their attributes can be more easily displayed and analyzed. However, this visualization is not as dense as squarified Treemaps.

• Crossings The crossing method places child nodes across the parent node, thereby only partially overlapping the parent. The Beamtree method [vHvW02] improves over the classic Treemaps when the hierarchical structure may be difficult to visually assess, while still being more space efficient than the adjacency techniques. The main drawback of this technique is that users are unfamiliar with this approach and that it is often less readable than other methods. way while still clearly presenting the data structure and emphasizing the content. The most prominent representative are "elastic hierarchies" [START_REF] Zhao | Elastic hierarchies: combining treemaps and node-link diagrams[END_REF]. In connection to interactive determination of the type of visual metaphor used for each part of the hierarchy, this technique allows for flexible analysis of the data using advantages of both representations.

Directed and Undirected Graphs

Techniques for displaying general graphs can be divided into three main groups: node-link based, matrix-based, and hybrid (see Figure 9). We discuss these in more detail below. A comparison of node-link and matrix techniques is presented by Ghoniem et al. [START_REF] Ghoniem | A comparison of the readability of graphs using node-link and matrix-based representations[END_REF]. According to the study, the advantages of node-link diagrams are their intuitiveness, compactness, and better suitability for path following tasks. They are more effective for smaller and sparse graphs. The Matrix representation inherently does not have edge crossings and node overlapping problems, and is thereby suitable also for dense graphs. When using appropriate node ordering, they can easily reveal dense substructures in the graph. However, they also suffer from scalability in limited display spaces, especially for very large graphs. In visual graph analysis, graph layout and matrix ordering influence the effectiveness of these representations. These issues are therefore in the core of graph visualization research.

Node-link representations

The main challenge is the layout (i.e., the placement of the nodes) so that graph readability and certain notions of graph aesthetics are supported (see Figure 10). Typical requirements include that the nodes do not overlap, the number of edge crossings is minimized, edge length is homogeneous, and in general, graph substructures are easily recognizable. This problem is intensively studied in the graph drawing community. Given these aesthetic goals and constraints, the aim is to find algorithms that efficiently provide good solutions.

Note that a specific group of graphs are graphs with geographic reference, such as transportation graphs. In this case, the nodes and possibly also edges of the graph have an inherent geographic location, which needs to be taken into consideration in their graphic presentation. Therefore, a specific graph layout algorithm is not needed for determining the position of each node on the screen. However, the fixed node position may exacerbate graph readability problems, such as crossings and long edges. Visualization of geographic data is a special research field, which we do not address here in detail. • Force-based layouts These techniques are based on a simulation of mechanical laws by assigning repulsive forces between nodes and attraction forces between endpoints of edges. Several forces have been described in the literature to achieve different properties of the layout. The seminal work of Eades uses an electric force between charged particles to model node repulsion and spring forces between the link endpoints to model edge attraction [START_REF] Eades | A heuristic for graph drawing[END_REF]. Fruchterman and Reingold [START_REF] Fruchterman | Graph drawing by force-directed placement[END_REF] have then improved the distribution of nodes by adaptation of the force models and Noack has further improved it with a more flexible set of force functions to achieve either a good space density or a good clustering of nodes. Kamada and Kawai [START_REF] Kamada | An algorithm for drawing general undirected graphs[END_REF] try to layout nodes such as the Euclidean distance between the nodes is proportional to the graph-theoretical distance. This family of layouts, however, does not scale well to graphs of thousands of nodes or more, due to their complexity. Therefore, improvements have been proposed. For instance, faster calculation of forces using an efficient GPU implementation [GHGH09], or using heuristics [START_REF] Frick | A fast adaptive layout algorithm for undirected graphs[END_REF] 10b). This algorithm and its variants are quite fast in practice and standard implementations such as [START_REF] Gansner | A technique for drawing directed graphs[END_REF] can easily layout several thousands of nodes in seconds. • Non-Standard Layouts Other approaches exist that combine the previous techniques or use completely alternative approaches to graph layouts. Projection of a node layout from high-dimensional to two-dimensional space has been proposed in [START_REF] Harel | Graph drawing by highdimensional embedding[END_REF]; although it is very fast in practice, the quality of the layout is very sensitive to the structure of the graph. For example, it is very effective for meshes and not effective at all for trees. LGL [ADWM04] first simplifies the graph by computing a spanning-tree; it then computes the layout iteratively in depth order using a force-directed layout.

LGL is able to scale to very large graphs (billions of vertices) thanks to the initial decomposition. It is very effective for quasi-trees but has not been thoroughly studied for other kinds of graphs; its results are very sensitive to the spanning-tree computation: choosing different spanning trees will results in quite different layouts for the same graph. The ISOM method [Mey98] applies the Self-Organizing Map algorithm [START_REF] Kohonen | Self-Organizing Maps[END_REF] for finding a suitable graph layout. As an alternative to costly layout computation, a graph layout visualization based on the semantics of the graph (on node labels) was presented in [START_REF] Shneiderman | Network visualization by semantic substrates[END_REF]. Semantically identical nodes (e.g., with the same labels) can be placed in boxes using standard layout algorithms (e.g., force-directed) (see Figure 11) or in layers using their importance for assigning the position within layers [GOB * 10]. Furthermore, attributes or prop-erties associated with graph vertices can be used directly to specify the position of these vertices, as with scatterplots [SA06, BCD * 10]: the layout computation is then straightforward and very fast. Combination of matrix and node-link approach Techniques using a combination of the two previous approaches aim at overcoming their limitations by focusing on their strengths. Three main approaches exist (see Figure 14).

• Multiple synchronized views These techniques link the matrix and node-link representation [START_REF] Henry | MatrixExplorer: a dualrepresentation system to explore social networks[END_REF]. Both views show the same data and are synchronized during exploration. Thereby, the user can concentrate on whatever view is more suitable for the current task.

• Matrix with link overlay The Matlink [START_REF] Henry | Matlink: Enhanced matrix visualization for analyzing social networks[END_REF] approach enhances matrix visualization with links at the border of the matrix (connecting the nodes). Using link highlighting, the paths can be easily spotted in the Matlink view and at the same time, the advantages of the matrix representation are retained. • Partial matrix and node-link representation There are two main approaches. Firstly, Nodetrix [START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF] combines both representations in one view, where node-link diagrams display the overall graph structure of the network, and adjacency matrices show communities. The work also discusses three ways of link display for this setting: aggregated links, underlying links, and underlying links with full size (see Figure 15). These forms can be also used for attributed links. Secondly, layered graphs (directed acyclic graphs) can be represented by so-called "quilts". They arrange nodes in a matrix-like form and connect them with orthogonal edges. In this way, a clear view of the graph is created [WBS * 08, BDF * 10].

Compound Graphs

Literature on visualization of graphs with hierarchic structure is relatively rare. We identify three main approaches.

Node-link graph visualization techniques These use node-link diagrams for the lowest hierarchy level and then use "bubbles" (enclosures) for various hierarchy levels. Examples include TugGraph [START_REF] Archambault | Tuggraph: Path-preserving hierarchies for browsing proximity and paths in graphs[END_REF] and Grouse-Flocks [START_REF] Archambault | Grouseflocks: Steerable exploration of graph hierarchy space[END_REF]. The advantage of this method is its intuitiveness. However, for large graphs with many links, this view gets easily overcrowded (see Figure 16 a). The edge overplotting problem can be partially solved by edge bundling [Hol06] (see Figure 12). Alternatively, only links between merged nodes can be drawn (see Figure 16 c).

Treemap-based A treemap visualization of the node hierarchy uses overlaid links between nodes [FWD * 03] (see Figure 16b). This approach may suffer from strong overplotting in case of many links between nodes of the hierarchy. Therefore, edge bundling is advised to improve the readability of the display [Hol06] (see Figure 12). Similarly, also onedimensional treemaps with links between nodes, so called ArcTrees [START_REF] Brodlie | Arctrees: Visualizing relations in hierarchical data[END_REF] can be employed (see Figure 16d), but these do not scale well for large hierarchies.

Matrix view with links These visualizations combine the generic node relationship visualization with a tree-based visualization of the hierarchic node relationships. This is an analogy to MatLink [START_REF] Henry | Matlink: Enhanced matrix visualization for analyzing social networks[END_REF]. This view is very clear, however, it may be difficult to understand the compound relationships between nodes (see Figure 16e).

Visual Representation of Dynamic Graphs

In this section, we discuss two categories of visual display of the time changes on graph elements: Using animation and . The static view is preferred for more detailed analysis of data changes. Static views that also incorporate the time-dimension of the data are more complex. In the following, we categorize the visualization techniques according to the type of data changes captured into those that affect only data attributes, and those that af-fect also data relationships. Please note that visual analysis of changes in dynamic graphs is related to comparing graphs. Graph comparison is discussed in Section 5.2. 17 c). When choosing the graph layout, the layout stability needs to be taken into consideration. E.g., in the treemap representations, the spiral layout [TS07] achieves a high continuity with high stability of the layout. Strip and pivot-by-middle layouts have also been shown to have higher layout suitability [START_REF] Bederson | Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies[END_REF]. All these layouts are preferable in spite of their higher aspect ratios in comparison to the squarified treemap. Furthermore, dynamic Voronoi treemaps [START_REF] Sud | Fast dynamic voronoi treemaps[END_REF] offer both good aspect ratios and stable layouts for displaying dynamic data. Alternatively, Tu and Shen [START_REF] Tu | Visualizing changes of hierarchical data using treemaps[END_REF] propose also static comparison of two time points in a treemap visualization (called contrast treemap).

Trees

Directed and Undirected Graphs

For attribute changes only, techniques for visualization of static graphs can be combined with visualizations of individual time dependent data items (e.g., color charts [START_REF] Saraiya | Visualization of graphs with associated timeseries data[END_REF]) are used (see Figure 18a). The advantage of this approach is the large number of the available graph layouts.

In case of structural changes, time-dependent graph layouts (animated graphs) need to be employed [CBTT95, Nor96, DGK01, EHK * 03, KG06]. In animated graph visualization (in analogy to animated tree visualization), a stable graph layout, which changes minimally, is of essence. A stable graph layout preserves the mental map of the user. It enables the user to follow changes on the screen [ELMS91, DGK01] and thereby it facilitates the analysis of graph changes. In laying out dynamic graphs, there is a large difference between strategies for drawing graphs with known histories and those that need to be adjusted in real-time depending on new data streams. A paper of Frishman and Tal [FT08] addresses this particular issue by proposing an online algorithm for dynamic layout implemented on the Instead of animation, Brandes and Corman [BC03] use the third dimension to show the evolution on time. GraphDice [BCD * 10] uses interaction to switch between projections where time can be mapped to one dimension.

Compound Graphs

There are only few techniques that visualize time-varying compound graphs. They employ either animation or static data representations.

Kumar et al.

[KG06] present a specific layout for animation of a node-link diagram with transparent "bubbles" for the hierarchic grouping of nodes (see Figure 19a). A static approach to visualization of dynamic compound digraphs using TimeArcTrees was presented by Greilich et al. [START_REF] Greilich | Visualizing the evolution of compound digraphs with TimeArcTrees[END_REF] (see Figure 19b). They show a sequence of node-link diagrams with horizontal node alignment in a single view, thereby supporting their direct comparison. TimeRadarTrees [START_REF] Burch | Timeradartrees: Visualizing dynamic compound digraphs[END_REF] use radial tree layouts for the hierarchy and a sequence of circle segments for representation of the temporal change of the structure (edges) of the Digraph (see Figure 19c). This view easily gets complex for larger graphs.

User Interaction in Graph Visualization

Interaction helps users solving tasks connected to exploration of graphs. These tasks can be of different nature such as topology-based or attribute-based [LPS * 06]. Topologybased tasks include finding adjacent nodes, or determining connections between nodes. Attribute-based tasks include, e.g., searching for nodes with specific values, and finding edges of certain types. For each task, one or more interaction techniques can be employed. Standard interaction techniques such as zooming, panning, or brushing and linking [CMS99, War00] are commonly used in graph visualization. In addition, specialized techniques have been developed for interactive visual graph navigation and exploration.

Interaction and exploration are deeply inter-related. Some graph analysis systems such as Pajek [START_REF] De | Exploratory Social Network Analysis with Pajek[END_REF] claim to support exploratory graph analysis by chaining complex operations on graphs without showing the intermediary results. However, Ahlberg et al. describe interactions and more specifically dynamic queries [START_REF] Ahlberg | Dynamic queries for information exploration: an implementation and evaluation[END_REF] as required to truly achieve exploration. The main reason is cognitive: exploring requires several hypothesis to be maintained in short-term memory which is very limited in capacity. Planning complex operations without feedback or using a textual syntax consumes all the short-term memory and exploration becomes impossible from short-term memory alone. Therefore, providing interactions with immediate feedback for the most frequent operations supports exploration. Other less frequent operation could still be done using more complex mechanisms, as explained in the next section on graph analysis.

The categorization of interaction techniques can be based on various criteria such as task, user intention [START_REF] Yi | Toward a deeper understanding of the role of interaction in information visualization[END_REF] or user action [START_REF] Elmqvist | Hierarchical aggregation for information visualization: Overview, techniques, and design guidelines[END_REF]. These criteria are interrelated. For example, one task may include performing several actions, or one task may correspond to several user intentions. Moreover, one user intention can be achieved by several user actions or, vice versa, an action can suit several intentions. For treemaps, the so-called balloon focus can be used for enlarging multiple items in a treemap [START_REF] Tu | Balloon focus: a seamless multi-focus+context method for treemaps[END_REF]. This approach keeps the form of other areas keeping relative position of items unchanged (see Figure 22).

We categorize interaction techniques according to stages in the Information

Visual Abstraction Interaction

In these approaches, the change of the visual presentation of the data concerns adjusting the type of visual presentation and its parameters.

Most of the graph visualization system provide standard dialog boxes and widgets to change the visual abstraction parameters, including the layout technique and its various parameters. Currently, very few systems allow the interactive manipulation of layout parameters, except using indirect manipulation such as sliders, list boxes, radio buttons and check boxes. Rich visualization systems provide a large number of these indirect manipulation widgets which use an important amount of the screen real-estate and force users to search for the right widget by reading their labels and trying to make sense of them, which can be quite long and tedious. This is why several research work is devoted to providing more direct mechanism change the parameters.

Changes of Visual Parameters

These techniques affect the parameters of the visual presentation. They include highlighting of items and other techniques.

Highlighting The emphasis of interesting items is a standard interaction technique. Recently, new techniques for highlighting a node and its neighborhood using hotbox and lasso selections were presented in [START_REF] Mcguffin | Interaction techniques for selecting and manipulating subgraphs in network visualizations[END_REF].

Brushing & Linking Multiple coordinated views are used to show the data from different perspectives. In these views, changes in one visualization (e.g., highlighting) are automatically transfered to the other views. For example, a matrix view coupled to a hierarchical view of the data can be used to reveal important information in the data [START_REF] Abello | Matrix zoom: A visual interface to semi-external graphs[END_REF].

Semantic Zooming Semantic zooming combines zooming with an increasing level of detail. In particular, graph aggregation can be used for gaining a coarser view on a large graph. The semantic zooming increases the level of detail by drilling down to lower levels of aggregation of the original data [EDG * 08, AvH04].

Changes of Visual Scheme

Changes of the visual scheme cover changing of the type of data visualization either by changing the layout or by changing the visual mapping.

Layout change

In node-link diagrams, layout change (adjustment) affects the positions of the data items on the screen (see Section 3). It can be performed by changing of the layout type with automatic recalculation of the new layout, by manual movement of nodes, or by adjusting the layout parameters including automatic readjustment of the layout. When concentrating on user-defined changes to graph layouts, an approach to easy selection and layout change of nodes and subgraphs was presented in [START_REF] Mcguffin | Interaction techniques for selecting and manipulating subgraphs in network visualizations[END_REF]. Furthermore, interactive adjustment of the layout constraints was presented in [DMW09a]. For matrix visualizations, user-driven reordering of matrix representation was described in [START_REF] Henry | MatrixExplorer: a dualrepresentation system to explore social networks[END_REF].

Change of visual representation

The change of the type of data presentation, e.g., from a matrix to a node-link diagram was presented in [START_REF] Zhao | Elastic hierarchies: combining treemaps and node-link diagrams[END_REF][START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF]. This change can affect the whole data view [START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF] (see Figure 23) or only a part of it [START_REF] Zhao | Elastic hierarchies: combining treemaps and node-link diagrams[END_REF][START_REF] Henry | NodeTrix: a hybrid visualization of social networks[END_REF]. By changing the visual representation, new insights into the data can be reached. In order to be able to follow the changes, smooth animations across transitions should be used.

Data Interaction

Data-level interaction affects the selection of the data to be displayed, or may change the data values and structure. Some operations can be done interactively but general graph analysis system provide more sophisticated mechanisms including scripting languages or powerful macro facilities to perform more complex operations.

Data Filtering

These interaction techniques influence which parts of the data set are displayed. The data filtering may follow three paths.

A top down approach This approach starts from the whole graph and then constrains the part of the data set to be visualized by filtering according to criteria or by manual data selection. The disadvantage of this approach is the need to show the whole graph at the beginning, which may require higher computational time for the layout and may lead to occlusions owing to the limited screen size. The advantage is gaining an overview of the graph structure first and then concentrating on interesting parts.

A bottom up approach This approach starts from one selected node [Fur86, AF07, vHP09] and successively shows more nodes/connections on demand. There are two main methods of choosing the additional nodes/edges to be displayed: based on graph structure, or based on a degreeof-interest function. The advantage of this approach is that only the most interesting part of the data set is visualized, however it is difficult to determine the starting point for the exploration and to define the degree-of-interest function. Therefore, we consider these methods in more detail.

• Navigation based on graph structure. These techniques reveal/hide that part of the graph that is determined by the connections between nodes. In graphs, neighborhood traversal shows neighbor nodes of a focus node up to a certain level [START_REF] Heer | Vizster: visualizing online social networks[END_REF]. For hierarchies, several traversal methods for have been described in [START_REF] Elmqvist | Hierarchical aggregation for information visualization: Overview, techniques, and design guidelines[END_REF]. The hierarchy traversal methods include: (1) above traversal, where nodes up to a certain level are shown; (2) below traversal, where nodes starting from a selected level are displayed;

(3) level traversal, where nodes at a certain level are displayed; (4) range traversal, where nodes in a range of levels are shown; and (5) unbalanced traversal, where certain branches of a tree are visible (see Figure 24). the middle coarsening level and the next interactive steps, graph algorithms are used (see Section 5).

Changes of data values

In these approaches, the change of the displayed data set result from direct data value manipulation. Specifically, the user can change the data values on one level or create/change graph aggregations.

Graph editing

The user can interactively delete or add nodes or edges directly in the visual interface. These graph editing actions trigger adjustment of the layout, while still maintaining the layout style and, where reasonable, the current layout topology. Graph editing affects the structural properties of the graph. In particular, the changes can affect specific types of subgraphs (so-called motifs). Automatic identification and highlighting of such structural changes was presented in [vLGRS09].

Interactive graph aggregation For simplification of graphs, graph aggregation is often used. The graph aggregation can be pre-defined, or determined interactively by the user [HF06, AMA08, AMA09]. For example, Grouse-Flocks [START_REF] Archambault | Grouseflocks: Steerable exploration of graph hierarchy space[END_REF] allows the user to add and remove aggregated nodes on demand (see Figure 25). This allows for variable views on the graph and its structure.

Graph Analysis

Algorithmic graph analysis is beneficial during all stages of the visual graph analysis process. Relevant techniques allow, e.g., to reduce a large graph to a smaller graph prior to visualization, to search for specific graph structures of interest, or to find similarities and dissimilarities for generating comparative graph views. In this section, we describe a number of graph analytical approaches.

Analysis of Graph Structure

In most user tasks, the analysis of the relationships between entities in the graph and the assessment of the global graph structure plays the key role. These tasks may be effectively supported by a combination of algorithmic graph analysis and interactive visualization. The algorithmic methods allow, e.g., to calculate node/edge properties, identify clusters in the graphs, etc., the results of which are visualized interactively. In the following, we summarize the methods according to user tasks starting from more simple to more complex tasks.

Identification of important nodes In networks, some nodes play a specific role owing to their position within the network. For example, so called hubs and authorities can be identified and visualized in the network, enabling faster analysis of the graph Analysis of connections between two nodes Besides focusing on single nodes, relations between two nodes can be analyzed, typically by calculation and highlighting of shortest paths between the entities. Usually, such analysis is combined with interactive selection of two entities of interest [HB05, HF07, TK08, GBD09] (see Figure 14b).

Graph Comparison

One specifically important analytical task is the examination of the similarities and differences between multiple graphs, especially focusing on structural aspects. Usually, structural differences are in the focus. Such difference may be identified by the identical node labels in both graphs, or by graph matching algorithms. After the matching, visualization is employed to explore the differences [START_REF] Andrews | Visual graph comparison[END_REF]. There are various types of analysis which we describe next.

One-to-one node comparison of two graphs Probably the most common task in graph comparison is the matching of individual nodes from one graph to individual nodes of the second graph. The VisLink visualization approach [START_REF] Carpendale | VisLink: Revealing relationships amongst visualizations[END_REF] was developed to support this task. It shows both graphs on separate planes in 3D, and draws matching links between corresponding nodes (see Figure 27a). For comparison of hierarchies, a similar approach, based on drawing the two hierarchies in opposite parts of the display and linking of their leaf nodes was proposed in [START_REF] Holten | Visual comparison of hierarchically organized data[END_REF] (see Figure 27b). In both cases, the visibility of matching links can be increased by edge bundling.

One-to-many nodes comparison of two graphs One-tomany nodes comparison concerns correspondence of one node in one graph to many nodes in another graph. Di Giacomo et al. [START_REF] Didimo | Visual analysis of one-to-many matched graphs[END_REF] developed a system that visualizes these one-to-many connections with low overlapping of links (see Figure 27c). , and overlapping of two networks with highlighting of common structural parts (see Figure 29a). Archambault [START_REF] Archambault | Structural differences between two graphs through hierarchies[END_REF] uses graph aggregation and graph filtering to reveal structural differences between two graphs (see Figure 29b).

Structural similarity among multiple graphs Structural comparison of multiple graphs is often based on their description by several graph properties such as graph size, density, connectedness etc. (see also Section 2.1). These properties can be used for exploration of large sets of graphs [START_REF] Freire | ManyNets: an interface for multiple network analysis and visualization[END_REF], or for the determination of structural similarity between graphs. Graph similarity may serve as an input for clustering of graphs (grouping similar graphs). Clustering helps gaining overview of types of graphs in large graph databases. Interactive combination of graph clustering and visualization of clustering results has been proposed in [START_REF] Von Landesberger | Visual analysis of graphs with multiple connected components[END_REF] (see Figure 30).

Concluding Remarks and Future Challenges

Research on visual graph analysis deals with the interrelated issues of graph drawing, graph presentation, humancomputer-interaction, and analytics. This state-of-the-art report represents an encompassing overview and systematization of recent developments in this field. Many advances have been made on individual parts of visual graph analysis. On the other hand, the surveyed literature discusses many important open challenges, that researchers see in need of work. In the following, we summarize key research challenges. The discussion of the relevant topics is divided into three broad areas: graph visualization and interaction, visual analysis systems, and conceptual issues.

Graph Visualization and Interaction

Scalability issues in graph drawing There has been much interest in the development of faster layout algorithms that produce more readable layouts for large graphs, also using parallel computing, as provided e.g., by current CPUs and GPUs. It is recognized that using a combination of automatic graph layout generation and user-oriented, interactive layout steering, better layouts can be obtained. As graphs get larger, graph filtering and aggregation have been the main means of graph simplification allowing to draw them. Alternatively, the limited screen space leading to strong overplotting in large graph visualization can be avoided by drawing graphs on large screens, where specialized layouts can be applied [MGL06]. It can be foreseen that work on more sophisticated graph layouts revealing the main structures in the whole graphs, or parts thereof, will continue. In particular, user involvement in the graph layout process involving analytical expertise of the user is a promising approach and may lead to easier interpretation of the drawings.

From an analytical perspective, also the understanding of the meaning of the nodes and edges, besides their global structure, is necessary. In particular, the readable/nonoverlapping drawing of nodes, edges and their labels is an important issue. When displaying graphs with labels, even smaller graphs can easily lead to overcrowded displays. This topic is gaining more interest in visual analytics research.

Graph types in graph drawing

In recent years, the variety of considered graph types has increased substantially. In particular, there has been a large amount of work on drawing dynamic and compound graphs. When drawing dynamic graphs, layout stability and on-line graph drawing are the main points of interest for the future research. In visual analysis, the understanding of the graph changes needs to be supported by stable layouts that preserve the mental map of the analyst thereby allowing them to follow changes on the screen [DGK01]. These layouts should be very stable for minor graph changes and, at the same time, be able to effectively show large graph changes. While a non-trivial challenge, if successfully supported it may lead to easier spotting of structural changes in the graph and thereby, more efficient and effective analysis. On-line graph drawing, where the data stream is unpredictable, poses major challenges in this respect.

Compound graphs as a combined graph type, including aggregated graphs, represent a complex data type. The main analytical problem there is the understanding of both types of connections in a graph, as well as the understanding of the graph structures on multiple abstraction levels. This is a very cumbersome task, which can be supported by graph visualization systems. However, the drawing of such complex graphs is still in its infancy.

In the future, also further graph types such as hypergraphs [KKS09], or graphs with overlapping sets of nodes [START_REF] Henry | Untangling euler diagrams[END_REF] may become more prominent in visual graph analysis research.

Graph uncertainty Graph visualization by now mainly deals with drawing graphs with given data, largely disregarding graph uncertainty. Visualization of uncertain data is a general challenge in visual analytics. As has been shown in [GS05], the degree of data certainty affects analytical decisions. Therefore, it is an important issue in visual graph analysis. In graph visualization, various types of uncertainty can be regarded. The uncertainty can relate to the graph structure (the existence of nodes and edges between them) and/or on graph attributes (edge and node attributes). For displaying node and edge attribute uncertainty, various methods from multivariate data visualization with uncertainty (see e.g., overviews given in [PWL97, THM * 05, GS06]) could be applied. However, their applicability to graph visualization needs to be studied. When dealing with structural uncertainty, there are few dedicated techniques. For example, Can-didTree [LRCP07] uses transparency and color for conveying uncertainty in merged graphs. Therefore, it is expected that more methods will be developed in the future to address graph uncertainty issues.

Perception issues in graph visualization

The understanding of graph structures in visualization strongly depends on human perception capabilities. Studies of human perception for graph drawing have recently focused on comparison of graph understanding using varying graph layouts. In graph design, studies on edge visualization have shown that the edge design has an influence on the graph reading. These various studies have given rise to new problems in graph visualization, which need to be studied in the future.

submitted to COMPUTER GRAPHICS Forum (1/2011).

Graph Interaction Techniques

In graph exploration, recently new interaction techniques for various graph types have been developed. These techniques increasingly make use of the structural properties of the graph to interactively navigate in the graph (e.g. in [START_REF] Tu | Balloon focus: a seamless multi-focus+context method for treemaps[END_REF]vHP09,[START_REF] Tominski | CGV-an interactive graph visualization system[END_REF]). This tendency supports the analytical purpose of graph visualization, as analysts can more easily examine the structural relationship between entities in the graph. In the future, this direction can be extended.

Visual Analysis Systems

Visual analysis systems In line with Keim's visual analytics process [KAF * 08], modern visual graph analysis systems should interactively integrate data pre-processing, interactive data visualization, and building and visualizing of data models for gaining knowledge from the data. Many visual analysis techniques already include parts of this process. However, many of them rely on black box computations (e.g., automatic graph pre-processing, automatic calculation of graph similarities or cliques). To support the variable hypothesis-insight-driven analytical process, more user involvement in the process should be aimed at. The user should have full control of the type of the analysis and its parameters. As this process includes multiple loops, interactive feedback possibilities are necessary. Therefore, integrated visual analysis systems should include such features.

Integration of various data types in visual analysis

Graphs as data structures capturing relationships between entities are part of a larger set of data types examined in various applications. Usually, the analysis of graphs is undertaken in combination with analysis of related data sets, or other data sets are transformed into graphs for their analysis [CGK * 07, BMGK08]. For analysis of the various data sets as a whole, the sole focus on visual graph analysis (in particular graph exploration) without taking other relevant data into account, is not suitable. In the future, larger integrated visual analytics systems combining research results from several areas are needed.

Addressing new analytical tasks With the increasing data set sizes and their complexity, new analytical tasks arise. For example, one such task is the examination of the similarities and differences between graphs. This task builds on the examination of the structure of one graph as discussed above. Lately, several papers about visual graph comparison for both trees and general graphs have been published (see Section 5). The comparison can concern only two graphs, trying to match nodes and edges between them. It can focus on finding similar graphs for one particular graph from a large set of graphs. It can concern gaining an overview of the types of structures in a large set of graphs. It can concentrate on analyzing the similarities of whole graphs or on matching of parts of one graph to other graphs. Owing to its complexity, and the variety of the problems, it is foreseeable that the research in this area will need to continue.

Collaborative visual graph analysis For solving complex analytical tasks concerning multiple large related data sets, a collaboration of several experts is necessary. Recently, the development of collaborative visual analysis systems has received attention [BMZ * 06, Kee06, Ise07]. However, collaborative visual graph analysis is not represented prominently. Therefore, the study of collaborative systems including graph data sets would be of advantage. The specifics of graph exploration, in particular, need to be studied.

Insight provenance for visual graph analysis In Visual

Analytics applications, the analytical processes are often long-running and/or distributed. To support the reproducibility, reversibility and automation of these processes, user tracking of the graph interaction steps is necessary. As a basis for tracking, a taxonomy of graph interaction techniques is necessary. The theory of interaction is a general Visual Analytics challenge [START_REF] Cook | A visual analytics agenda[END_REF]. Although several interaction taxonomies also for insight provenance have been recently introduced [GZ08, HMSA08], their applicability and the need for their adaptation to graph analysis needs to be studied. In return, specific classifications of graph interaction techniques could be developed. In this report, we have aimed to classify them for gaining a concise overview of the current state of the research. This classification, however, may not be directly applicable to user tracking applications.

Applications For analytical purposes, standard graph visualization and analysis methods need to be adapted to the specific needs of the particular application domain.

For example, there are specialized systems for visualization of bio-chemical structures, shareholding structures, and many more. Designing graph visualization systems with fast adaptability to various data types, analytical tasks and application-dependent analytical processes is still a challenge. Even within one application, often, the network to be analyzed needs to be constructed from heterogeneous data sources, and the focus of interest (attributes of nodes and edges) varies dynamically. Designing such systems is obviously not trivial. This method offers insights into the usability of the systems in real world scenarios, however does not allow for standardized quantitative comparison of the techniques. The choice of appropriate evaluation method and its design is still discussed in the community.

Conceptual Issues

Taxonomies and benchmarks The field of visual graph analysis would profit from more elaborate taxonomies for tasks, interaction, visualization techniques, measures for quality, and benchmarks for comparing the new techniques. They would support both the design and development of visual analytic systems and their evaluation. Although several taxonomies and sample data sets exist, a more broader scope of theory and data aspects is needed owing to the large set of problems/tasks in visual analysis of graphs.

Figure 1 :

 1 Figure 1: The main components of visual graph analysis considered in this report.

Figure 2 :

 2 Figure 2: The Visual Analytics process by Keim et al. [KAF * 08] with the four key steps 1: data pre-processing, 2: mapping/layout 3: visual user interaction 4: model-based analysis. c 2008 Springer-Verlag Berlin Heidelberg.

Figure 3 :

 3 Figure 3: Classification of graphs according to their time dependence and graph structure.

  The number of nodes (i.e., graph order) is often referred to as graph size (|V |). Graph density is the number of edges relative to the maximum potential number of edges D = 2|E| |V |(|V |-1) . Sparse graphs have around O(|V |) < |E| << O(|V | 2 ) edges, while dense graphs show density values close to one. Graphs with the maximum number of edges are called complete graphs. A clique is a subset of a graph that is fully connected.

  (a) Original graph (b) Stochastic edge sampling (c) Geodesic clustering (d) Structure-based filtering

Figure 4 :

 4 Figure 4: Example of various graph reduction techniques. The graphs are visualized using the GEM layout [JHGH08]. c 2008 IEEE.

Figure 5 :

 5 Figure 5: Graph aggregation for multi-scale graph visualization [EDG * 08]. c 2008 IEEE. Top: Graph aggregation schema showing several levels of aggregation. Darker rectangles show the corresponding data areas in the aggregation. Bottom: Example of graph aggregation using a matrix visualization.

  (a) Node-link diagram (b) Space-filling diagram (c) Combined representation

Figure 6 :

 6 Figure 6: Three types of hierarchy visualization techniques. a) Node-Link, b) space-filling, c) hybrid. [ZMC05], c 2005 IEEE.

Figure 7 :

 7 Figure 7: Examples of node-link tree visualizations. a) Phyllotrees [NCA06], c 2006 IEEE. b) Point-based tree [SSH09], c 2009 IEEE.

•

  Enclosures These techniques recursively layout child nodes within the area of their parent nodes. The most prominent examples are Treemaps -rectangular shapes recursively subdividing rectangular display space according to the underlying hierarchy, introduced by Shneiderman[START_REF] Shneiderman | Tree visualization with tree-maps: 2-D space-filling approach[END_REF] (so called slice-and-dice algorithm). Variants include Voronoi tessellations[START_REF] Balzer | Voronoi treemaps for the visualization of software metrics[END_REF] or bubble layouts [Bed01]. Other types, such as elliptic[START_REF] Otjacques | CGD -a new algorithm to optimize space occupation in ellimaps[END_REF] or circular shapes have been proposed, but they do not lead to fully space filling visualizations. The main advantage of enclosures is the very good usage of the available space, as the child nodes do not need extra space owing to the overlap with the parent nodes. The disadvantage is that the overlapping of the parent nodes may also lead to a more difficult distinction of the hierarchy structure by the user, as it is rather implicitly encoded. For Treemaps, several advanced layout techniques have been developed including ordered (i.e., pivot-based)[START_REF] Bederson | Ordered and quantum treemaps: Making effective use of 2D space to display hierarchies[END_REF], squarified [BHvW99], and spiral [TS07] Treemap layouts. For example, squarified Treemaps aim at generating subrectangles of square-like aspect ratios, supporting easier comparison of sizes and presentation of additional diagrams or other elements within the rectangles. According to Tu and Shen[START_REF] Tu | Visualizing changes of hierarchical data using treemaps[END_REF], the slice-and-dice algorithm leads to high aspect ratios with good readability. Strip, pivot-based and spiral techniques have medium aspect ratios with medium readability. Squarified Treemaps have very good (low) aspect ratios but low readability. In order to better distinguish the hierarchical structure, cushion Treemaps[START_REF] Van Wijk | Cushion treemaps: visualization of hierarchical information[END_REF] apply shading of the shapes. Treemaps that reflect the geographic distribution of the hierarchical data were presented in[START_REF] Wood | Spatially ordered treemaps. Visualization and Computer Graphics[END_REF].• Adjacency In contrast to Treemaps, adjacency-based techniques do not overlap the parent nodes by child nodes, but represent the node relationships by placing the child nodes next to their parent nodes. The placement can be in circular layers, such as in the SunBurst method [SZ00],

Figure 8 :

 8 Figure 8: Three types of space filling hierarchy visualization techniques. a) Enclosure: Cushion Treemap [vWvdW99], c 1999 IEEE. b) Adjacency: Icicle plot [TS08a], c 2008 IEEE. c) Crossing: BeamTrees [vHvW02], c 2002 IEEE.

Figure 9 :

 9 Figure 9: Three types of general graph visualization techniques: a) Node-link diagram, b) adjacency matrix, c) hybrid. From [HFM07], c 2007 IEEE.

  When no position is inherently associated with vertices, a graph layout algorithm is required. The graph layout research field is very large, and an extensive survey of proposed techniques is beyond the scope of this report. The latest survey from Herman et al. dates from 2000 [HMM00] and several new algorithms have appeared since then. The related work part in [AAM07,MM08] as well as the comparison in [HJ07] nicely summarize many current techniques. In our report, we classify the techniques according to the type of node placement.

  (a) Multi-level graph layouts (b) Dig-Cola layout

Figure 10 :

 10 Figure 10: Graph layout examples. a) A comparison of multi-level graph layouts GRIP, FM 3 and Topolayout [AAM07]. c 2007 IEEE. b) Layered layout of cyclic directed graph [DK05]. c 2005 IEEE.

Figure 11 :

 11 Figure 11: Graph visualization using data semantics [SA06]. c 2006 IEEE.

Figure 13 :

 13 Figure 13: Examples of matrix reordering on graph presentation. a) Using HDE algorithm. b) Using NNTSP reordering. From [EDG * 08], c 2008 IEEE.

Figure 14 :

 14 Figure 14: Examples of combined matrix and node link graph visualization techniques. a) Multiple linked views [HF06]. c 2006 IEEE. b) Links connected to the matrix view [HF07]. c 2007 Springer-Verlag Berlin Heidelberg. c) Node-link and matrix combined -part and part [HFM07]. c 2007 IEEE.

Figure 15 :

 15 Figure 15: Three ways of link visualization in a combined node-link and matrix data representation using the NodeTrix approach [HFM07]. c 2007 IEEE.

Figure 16 :

 16 Figure 16: Visualization techniques for compound graphs [Hol06], c 2006 IEEE. (a) Node-link visualization with grouped nodes in "bubbles". (b) Links overlaying a treemap visualization.(c) Compound drawing using enclosures and links between merged nodes. (d) ArcTreeslinks overlaying a 1D treemap [BDJ05]. (e) A matrix view for showing relations between entities linked with tree view of the nodes as in MatLink approach[START_REF] Henry | Matlink: Enhanced matrix visualization for analyzing social networks[END_REF].

  (a) Time line tree (b) Treemap with time series (c) Animated circular icicle plot

Figure 17 :

 17 Figure 17: Visualization of time-dependent trees. (a) Time line tree [BBD08], c 2008 ACM. (b) Time series in the treemap nodes [DHKS05], c 2005 IEEE. (c) Animated hierarchic circlular plots [TS08a], c 2008 IEEE.

  (a) Node-link diagram with time series in nodes (b) Animated node-link diagram

Figure 18 :

 18 Figure 18: Visualization of time dependent graphs. (a) Time series in nodes [SLN05], c 2005 IEEE. (b) Animated graphs [FT08], c 2008 IEEE.

  Frishman and Tal [FT04] present a layout which focuses on maintaining the clustered structure during the animation. The groups of nodes are displayed using bounding boxes around the groups. Reitz et al. [RPD09] use dynamic graph layouts for showing areas of interest in dynamic compound graphs. submitted to COMPUTER GRAPHICS Forum (1/2011).

Figure 19 :

 19 Figure 19: Visualization of time varying compound graphs. (a) Animated graphs by Kumar et al. [KG06], c 2006 IEEE. (b) TimeArcTrees [GBD09], c 2009 held by the authors. (c) TimeRadarTrees [BD08], c 2008 held by the authors.

  Visualization reference model of Card at al.[START_REF] Riedl | An operator interaction framework for visualization systems[END_REF][START_REF] Card | Readings in Information Visualization: Using Vision to Think[END_REF] and user actions.The reference model has three stages: data, visual form (a.k.a visual abstraction) and view. The classification criterion is whether the user action affects the data (the selection of the displayed data or the data values), the visual display of the data (visual parameters or visual representation), or the view. Data, visualization and view manipulation can be used for interactive data exploration and navigation. This categorization follows the idea of Elmqvist and Fekete[START_REF] Elmqvist | Hierarchical aggregation for information visualization: Overview, techniques, and design guidelines[END_REF] andBertini and Lalanne [BL09]. Please note that these three types of interaction are sometimes closely connected. For example, data manipulation may automatically lead to changes of visual parameters (e.g., data filtering can influence the graph layout, or zooming can be combined with data filtering forming a type of semantic zooming). 4.1. View Interaction Panning and Zooming Panning and zooming allow to navigate in any direction and change the zoom-level in the view. For node-link diagrams, a specific type of panning (guided panning) has been proposed. It allows to navigate along edges of a selected node and thereby to explore the structure of the graph. It can be combined with automatic zooming on the edge and distortion of end-node position closer to the currently selected node [MCH * 09]. Magic Lenses Owing to the limited display space, showing the whole data set may lead to strong overplotting or very small (up to, unreadable) data items. Magic Lenses [BSP * 93], including distortion techniques change the representation or allocate more space to items in focused areas and thereby, improve the readability of the data of interest. They are used both for node-link and space filling graph visualization techniques. The changes can concentrate either on one area or on multiple areas of the screen. For geometric changes, the technique is called fisheye views. Interactive selection of the focus area helps to explore different parts of the data in more detail.• Single focus Graphical fisheye views were introduced in [SB92]. So called edge lenses resolve strong overlaps of edges in the view. They displace the edges to a larger area[START_REF] Wong | Edgelens: an interactive method for managing edge congestion in graphs[END_REF] (see Figure20). This approach is especially useful for geographic-based graphs, where node repositioning is not desired and therefore, cannot help to solve edge overlap. Another approach uses filtering of interesting edges in a specified area, or moving neighbor nodes closer to a selected node relying on the graph structure [MCH * 09]. This type of node position change can be combined with geometric view distortion[START_REF] Tominski | Fisheye tree views and lenses for graph visualization[END_REF] (see Figure21). In node-link visualization of hierarchies, a degree-of-interest function can be used for allocating more area to more interesting parts of the tree, e.g., in DOITrees [CN02, HC04]. None-geometric magic lenses include Excentric Labels and Color Lenses. Excentric Labels [FP99, BRL09] show labels or other statistics for items contained in dense focus regions (nodes or matrix cells). The information is displayed outside the focus region with connectors linking the nodes/cells to their related label. Color Lenses [EDF10] dynamically adapt the color range of items inside the focus region to better use the screen color range when mapping values with a very large dynamic to the color of nodes or matrix cells. • Multiple foci Multiple foci distort several view areas at the same time. It is useful for comparing various parts of the display or focusing on several items that are spread across the view. In node-link diagrams either magnification of the areas of interest [SZG * 96,TS99] or space folding (shrinking of area out of focus) can be used [MGT * 03, ERHF09] (see Figure 28 bottom right).

Figure 20 :

 20 Figure 20: Example of edge lens interaction. (a) Original view without lens. (b) Using edge lens From [WCG03], c 2003 IEEE.

Figure 21 :

 21 Figure 21: Examples of different types of edge lens interactions. (a) Original view without lens. (b) Using local edge lens. (c) Using bring neighbors lens. (d) Using composite lens which combines (b), (c) and Fisheye lens. From [TAvHS06], c 2006 IEEE.

Figure 22 :

 22 Figure 22: Multiple foci in a treemap. (a) Original view. (b) Using balloon focus. From [TS08b], c 2008 IEEE.

Figure 23 :

 23 Figure 23: Transformation of visual representation of a graph from node-link to matrix view. The picture shows five stages of this process [HFM07], c 2007 IEEE.

Figure 24 :

 24 Figure 24: Hierarchy traversal strategies [EF09], c 2009 IEEE. (a) above traversal, (b) below traversal, (c) level traversal, (d) range traversal. (e) unbalanced traversal.

Figure 25 :

 25 Figure 25: Interactive editing of a graph hierarchy. a) Creating a new aggregation node by merging of nodes. b) Deleting an aggregation node, thereby revealing the underlying merged nodes. From [AMA08], c 2008 IEEE.

  [START_REF] Ovalle-Perandones M | Hubs and authorities in a spanish co-authorship network[END_REF]. The importance of nodes and edges is measured by derived quantities (i.e., network metrics) such as centrality-based measures [Fre79] and ranking-measures[START_REF] White | Algorithms for estimating relative importance in networks[END_REF]. Network metrics can help the analysts to explore networks. Color coding of nodes or edges by metric values, or displaying metrics and networks in multiple linked views (as lists, scatterplots, or parallel coordinates) are used in this respect. They offer the possibility to interactively chose the metrics of interest and to filter/highlighting nodes according to these metrics [CJM04, PS06, BCD * 10, VMCJ10].

Figure 26 :

 26 Figure 26: Interactive graph motif search and visualization. From [vLGRS09], c 2009 held by the authors.

Figure 27 :

 27 Figure 27: Visualization of graph comparison. a) Oneto-one graph matching [CC07], c 2007 IEEE. b) One-toone hierarchy matching [HvW08], c 2009 held by the authors. c) One-to-many graph matching [GDLP09], c 2009 Springer-Verlag Berlin Heidelberg.

Figure 28 :

 28 Figure 28: Tree comparison. a) Schema of the tree comparison. b) Example of tree comparison using highlighting of tree differences. The left view shows the traditional view, the right view is distorted in order to emphasize important parts of the tree [MGT * 03], c 2003 ACM

Figure 29 :

 29 Figure 29: Visualization of structural differences between two graphs. a) A schematic illustration of graph difference. b) Visualization of graph differences using network overlapping [FHK * 09], c 2009 IEEE. c) Visualization of graph differences using difference hierarchies [Arc09], c 2009 held by the author.

Figure 30 :

 30 Figure 30: SOM-based graph clustering for analysis of types of graph data space and similarities between graphs [vLGS09], c 2009 IEEE.

  In addition, there are specialized graph drawing techniques, which use new graph visualization techniques. Two main examples are: graph splatting and graph maps. The first one forms graphs as two-dimensional scalar fields [vLdL03]. The second one visualizes graphs as maps [GHK10], where the relationships between nodes are represented as adjacency between neighboring areas (nodes). Both approaches create an approximate representation of a graph.

  Evaluation Evaluation of usability and user acceptability of the techniques including development of the evaluation methodologies is an important future challenge for the Visual Analytics research area [KMS * 08, TC05, TC06, LK07]. Currently, there is a broad discussion in the Visual Analytics community on the appropriate methodology for the evaluation of Visual Analytics and information visualization systems. This discussion applies also to the visual analysis of graphs. This challenge is expressed in the words ofPlaisant et al. in the introduction to the special issue of Computer Graphics and Applications [PGS09] "Assessing VA [Visual Analytics] technology's effectiveness is challenging because VA tools combine several disparate components, both low and high level, integrated in complex in-teractive systems used by analysts, emergency responders, and others. ... Traditional evaluation metrics such as task completion time, number of errors, or recall and precision are insufficient to quantify the utility of VA tools, and new research is needed to improve our VA evaluation methodology.". When concentrating on the evaluation of graph visualization techniques, several approaches have been proposed, ranging from quantitative to qualitative studies. Controlled experiments measuring accuracy and duration of user tasks have been used, for example, to compare tree visualization techniques [Kob04, AK07, ZK08]. An extension of these two main measures, the so-called cognitive load measure was used for evaluating general graph visualizations[START_REF] Huang | Measuring effectiveness of graph visualizations: a cognitive load perspective[END_REF]. Moreover, tracking can be employed for quantitative evaluation, e.g., for comparing graph layouts[START_REF] Huang | Using eye tracking to investigate graph layout effects[END_REF][START_REF] Pohl | Comparing readability of graph layouts using eyetracking and task-oriented analysis[END_REF]. These controlled studies offer a quantitative comparison across techniques, however often suffer from the focus only on selected low level tasks. Note that the formulation of these tasks can influence the comparison result[START_REF] Ziemkiewicz | The shaping of information by visual metaphors[END_REF]. A combination of quantitative and qualitative study has been performed for comparing graph layouts produced by both in a manual and in an algorithmic way [DLF * 09]. The subjective user view has been used for ranking of best layouts. A qualitative view on the effectiveness of visual analytics techniques can be gained by use case studies conducted by domain experts (e.g., in [PS08, MGT

* 03]

).

submitted to COMPUTER GRAPHICS Forum (1/2011).

Acknowledgements

We thank Vyara Ivanova, Anna Mitkova, Melanie Görner, and Robert Rehner for their helpful comments and suggestions. We are grateful to the anonymous reviewers for their constructive and useful comments. We thank all authors and copyright holders of the original figures for agreeing to their reproduction in this paper. This work was partially supported by the German Federal Ministry of Economics and Technology within the THESEUS project (http://www. theseus-programm.de/). It was also partially supported by the German Research Foundation (DFG) within the project Visual Feature Space Analysis as part of the Priority Program on Scalable Visual Analytics (SPP 1335).