Information Technology Reference
In-Depth Information
2
1
2
5
6
1
2
1
−
2
−
1
2
1
1
−
1
2
0
3
2
Fig. 1.
Example of a calculation graph. Edgeweights are indicated on the edges
Further Examples.
There are many other scenarios in which most of the information of
alarge graph should be presented in a limited area. A first example are social networks,
which are usually quite large. In this setting, vertices usually have labels and weights;
the weight may describe the person's activity in the network. By drawing aheavysub-
graph in a restricted area, a user can quickly get an overview over important actors in
the network and connections between them. A second example, which we will use in
the main part of the paper, are coauthor networks, where the weights represent numbers
of publications. Here, we want to find a drawing of a subgraph that represents as many
of the publications as possible, i.e., we prefer to keep authors with many publications.
Related Work.
Surprisingly, the very natural problem of selecting asubgraph that can
be drawn within a prescribed area seems to be new. Some work on related problems,
however, is worth being mentioned. Rather than fixing the drawing area and maximiz-
ing the size of the subgraph that fits into this area, graph drawing research has focussed
on drawing the whole input graph and minimizing the area needed for the drawing,
which has also been the task in some graph drawing contests [6]. This problem is called
compation and known to be NP-hard for orthogonal drawings with given orthogonal
representation (that is, fixed bends) [14]. In constrained graph layout[12,9],theuser
can constrain the region into which a vertex must be placed. Dwyer et al. [8] presented
the algorithm IPSep-CoLa where constraints demanding a vertical or horizontal sepa-
ration of vertex labels can be specified. Such constraints make it possible to enforce
that vertices are placed within a prescribed rectangular area. However, in contrast to our
work, they do not consider dropping vertices. If the vertices do not fit into the area, their
algorithm will not find a feasible drawing. The well-known algorithm of Fruchterman
and Reingold [10] for force-directed graph drawing allows to specify a rectangular area
within which the whole graph has to be drawn. However, in contrast to our work, the
algorithm can easily achieve this since vertices are drawn as points without labels and
edges can be made arbitrarily short, which we do not allow.
Dwyer et al. [7] developed a method for interactive exploration of graphs based on
constrained graph layout. They use a fast heuristic for the overview drawing;forthe
detailed view of a smaller part of the graph, however, they can afford to use a slower
constrained graph layoutalgorithm that yields better results. Constraints ensure con-
sistency between the views and preserve the users's mental map. Da Lozzo et al. [5]
considered the problem of drawinggraphs on the very small display of a smartphone.
They did not try to represent the whole graph on the display, but rather decided to pro-
vide only a local view around a focus vertex; their approach then offers interactive ways
of navigating throughthegraph and exploring the graph based on the local view.
