Information Technology Reference
In-Depth Information
Drawing Graphs within Restricted Area
Maximilian Aulbach
1
, Martin Fink
2
,Julian Schuhmann
1
, and Alexander Wolff
1
1
Lehrstuhl f ur Informatik I, Universitat W urzburg,Germany
2
Department of Computer Science, University of California, Santa Barbara, USA
Abstract.
We study the problem of selecting amaximum-weight subgraph of a
given graph such that the subgraph can be drawn within a prescribed drawing area
subject to given non-uniform vertex sizes. We develop and analyze heuristics both
for the general (undirected) case and for the use case of (directed)
calculation
graphs
which are used to analyze the typical mistakes that high school students
make when transforming mathematical expressions in the process of calculating,
for example, sums of fractions.
1
Introduction
Our motivation for the problem that we study in this paper stems from so-called
calcu-
lationgraphs
.Calculation graphs represent calculations starting from some initial task.
They are usedinstudies [13] involving largenumbers of high school students in order
to analyze the students' typical mistakes in elementary mathematics. Even for relatively
simple tasks such as evaluating the term “3
(2 + 1
/
5)”, the different transformations
performed by a largenumber of subjects can result in calculation graphs with hundreds
of vertices. With the help of drawings of calculation graphs, human experts can ana-
lyze how students calculate and, in particular, which mistakes they frequently make.
As Hennecke [13] suggests, such drawings are only useful if they are not too large,
that is, if they fit into a relatively small drawing area. Hence, well-readable drawings
of important parts of the graphs must be generated in an automated fashion. Certainly,
the drawn subgraph should represent as much information of the original calculation
graph as possible. Therefore, we consider the graphs to be edge- and vertex-weighted;
see Fig. 1 for an example. The weight of an edgeisthenumber of students who applied
the respective calculation step; the weight of a vertex is the number of students who had
the given term as an intermediate result in their calculation. Since we want the labels
of the vertices to be readable, we assume that their sizes are fixed. Hence, often only a
small fraction of the graph will fit into the prescribed drawing area. Note that a user of
such a drawing must be made aware that only a subgraph is shown.
Certainly, vertices and edges that occur only in a single student's calculation can
easily be dropped. For higher weights, however, this is not as easy. For instance, it
is conceivable that dropping asingle vertex of weight
W
makes it possible to include
several other vertices into the drawing, each of weight slightly less than
W
; then the
resulting drawing potentially allows for a better analysis. Hence, we need to select
the subgraph to be drawn based on the graph structure and not only on the weights.
M. Fink was partially supported by a fellowship within the Postdoc-Program of the German
Academic Exchange Service (DAAD). A. Wolff acknowledges support by the ESF EuroGIGA
project GraDR (DFG grant Wo 758/5-1).
·
