Information Technology Reference
In-Depth Information
that now ouredges are directed since they represent calculation steps. Additionally, we
are given a
start vertex s
∈
V
that represents the task given to the students. Hence,
s
must
be present in the outputdrawing and, furthermore, we insist that in the subgraph that is
finally drawn, each vertex can be reached from
s
.Tofurther improve the readability of
the steps, we want as many edges as possible pointing from left to right. As a drawing
convention for the edges, we will use the orthogonal drawing style with edges leaving
vertices horizontally; we try to minimize the numbers of crossings and of bends and to
optimize the gaps between edges and vertices. The hardness proof for general graphs
can easily be adjusted. Hence, the problem remains NP-hard.
3.1
Our Algorithm
Duetotherequired readability from left to right, our approach is based on the Sugiyama
framework [17] for hierarchical graph drawing. This framework consists of several steps
that we will adjust to our problem. Ouradjustments are optimized for ourdrawing style
and especially for the task of removing vertices or edges from the graph, if necessary.
We first briefly review the steps of the Sugiyama framework before going into detail
and describing ouradjustments.
In the first step, the graph is made acyclic by reverting some of the edges. Next, the
vertices are assigned to layers from left to right. Then, based on the layer assignment,
the number of edge crossings is minimized resulting in relative orders of the vertices of
each layer. Eventually, final vertex coordinates are computed and the edges are routed.
Breaking theCycles.
In later steps of the Sugiyama framework, it is assumed that all
edges are directed from left to right, i.e., the graph must be acyclic. Hence, we must
revert some edges. For reverting the smallest number of edges, the NP-hard Feedback
Set problem must be solved. We can either use existing heuristics, or even afford solving
the problem optimally with the help of an MIP solver; in our tests, this worked quite
fast and allows us also to minimize the weight of the reverted edges rather than their
number.
Layer Assignment.
Several approaches for the layer assignment in the Sugiyama frame-
work exist, depending on the objective, e.g., of minimizing the number of layers or the
number of vertices in a layer. Often, the number of layers is minimized subject to a
prescribed maximumheight of each layer. However, we will not use the height of our
drawing area as the maximumheight of a layer, although, at first, this may seem a good
idea: If we do so, we would most probably have to remove many layers of vertices com-
pletely from the graph in later steps, which, subsequently, can also cause the removal of
vertices of layers that are not removed, making these layers automatically smaller. In-
stead, we will set
n
max
=
,where
k
is the length of the longest path in the graph,
so that we can hope for roughly equal numbers of vertices per layer. We mainly used the
heuristic of Coffman and Graham [4] with the minor adjustment that preferably the left-
most layers have more vertices; we also tested Graham's list scheduling algorithm [11]
andanassignment with the minimumnumber of layers.
|
V
|
/
k
Ve r t ex Removal.
After the layer assignment, the configuration usually does not fit into
the drawing area. We now remove vertices until all vertices can be placed in the drawing
