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 editors