Hierarchical Graph Models and Infor

Hierarchical Graph Models and Information Visualizaion
Victor N. Kasyanov
Laboratory of Program Construction and Optimization
A.P. Ershov Institute of Informatics System
Novosibirsk, 630090, Russia
e-mail: kvn@iis.nsk.su

Abstract—Graphs are the most common abstract structure
encountered in computer science. Many modern systems,
particular for graphics workstations, include structural
information visualization. In this paper, we consider practical
and general graph formalism called hierarchical graphs and
present the Higres and Visual Graph systems aimed at
supporting of information visualization on the base of
hierarchical graph models.
Keywords-hierarchical graph; graph drawing; information
visualization

I. INTRODUCTION
Graphs are used almost everywhere in computer science
and programming [13]. Any system that consists of discrete
states (or sites) and connections between them can be
modeled by a graph.
Graph models can be effectively used in practice only
along with support tools that provide visualization, editing
and processing of graphs. For this reason many graph
visualization systems, graph editors and libraries of graph
algorithms have been developed in recent years. Examples of
these tools include VCG [16], daVinci [5], Graphlet [10],
GLT&GET [15], yEd [19 ] and aiSee [1].
In some application areas the organization of information
is too complex to be modeled by a classical graph. To
represent a hierarchical kind of diagramming objects, some
more powerful graph formalisms have been introduced, e.g.
higraphs [6] and compound digraphs [17]. The higraphs are
an extension of hypergraphs and can represent complex
relations, using multilevel "blobs" that can enclose or
intersect each other. The compound digraphs are an
extension of directed graphs and allow both inclusion
relations and adjacency relations between vertices, but they
are less general then the higraph formalism. One of the
recent non-classical graph formalisms is the clustered graphs
[4]. A clustered graph consists of an undirected graph and its
recursive partitioning into subgraphs. It is a relatively
general graph formalism that can handle many applications
with hierarchical information, and is amenable to graph
drawing.
Hence, there is a need for tools capable of visualization
of such structures. Although some general - purpose graph
visualization systems provide recursive folding of subgraphs,
this feature is used only to hide a part of information and
cannot help us to visualize hierarchically structural
information. Another weak point is that usual graph editorsdo not have a support for attributed graphs. Though the GML
file format, used by Graphlet, can store an arbitrary number
of labels associated with graph elements, it is impossible to
edit and visualize these labels in the Graphlet graph editor.
The standard situation for graph editors is to have one text
label for each vertex and, optionally, for each edge.
The size of the graph model to view is a key issue in
graph visualization [8]. Large graphs pose several difficult
problems. If the number of graph elements is large it can
compromise performance or even reach the limits of the
viewing platform. Even if it is possible to layout and display
all the graph elements, the issue of viewability or usability
arises, because it will become impossible to discern between
nodes and edges of graph model. It is well known that
comprehension and detailed analysis of data in graph
structures is easiest when the size of the displayed graph is
small. Since none of the static layouts can overcome the
problems caused by large graphs, hierarchical presentation,
interaction and navigation are essential complements in
information visualization.
In the paper, we consider a practical and general graph
formalism called hierarchical graphs and graph models [11].
It is suited for visual processing and can be used in many
areas where the strong structuring of information is needed
[14]. We present also the Higres and Visual Graph systems
that are aimed at supporting of information visualization on
the base hierarchical graph modes. The Higres system is a
visualization tool and an editor for attributed hierarchical
graphs and a platform for execution and animation of graph
algorithms [9]. The Visual Graph system was developed to
visualize and explore large attributed hierarchical graphs that
present the internal structured information typically found in
compilers [18].