Compact Layered Drawings
of General Directed Graphs
Adalat Jabrayilov1 , Sven Mallach3 , Petra Mutzel1 ,
Ulf Rüegg2 , and Reinhard von Hanxleden2

arXiv:1609.01755v1 [] 29 Aug 2016

1

3

Dept. of Computer Science, Technische Universität Dortmund,
Dortmund, Germany
{adalat.jabrayilov,petra.mutzel}@tu-dortmund.de
2
Dept. of Computer Science, Kiel University, Kiel, Germany
{uru,rvh}@informatik.uni-kiel.de
Dept. of Computer Science, Universität zu Köln, Köln, Germany
mallach@informatik.uni-koeln.de

Abstract. We consider the problem of layering general directed graphs
under height and possibly also width constraints. Given a directed graph
G = (V, A) and a maximal height, we propose a layering approach that
minimizes a weighted sum of the number of reversed arcs, the arc lengths,
and the width of the drawing. We call this the Compact Generalized Layering Problem (CGLP). Here, the width of a drawing is defined as the
maximum sum of the number of vertices placed on a layer and the number
of dummy vertices caused by arcs traversing the layer. The CGLP is NPhard. We present two MIP models for this problem. The first one (EXT)
is our extension of a natural formulation for directed acyclic graphs as
suggested by Healy and Nikolov. The second one (CGL) is a new formulation based on partial orderings. Our computational experiments on
two benchmark sets show that the CGL formulation can be solved much
faster than EXT using standard commercial MIP solvers. Moreover, we
suggest a variant of CGL, called MML, that can be seen as a heuristic
approach. In our experiments, MML clearly improves on CGL in terms
of running time while it does not considerably increase the average arc
lengths and widths of the layouts although it solves a slightly different
problem where the dummy vertices are not taken into account.
Keywords: layer-based layout, layer assignment, mixed integer programming

1

Introduction

A widely used hierarchical drawing style for directed graphs is the method proposed by Sugiyama et al. [10] that involves the following steps in this order: (i)
cycle removal, (ii) layering phase, (iii) crossing minimization, and (iv) coordinate
assignment and arc routing. One of the consequences of this workflow is that it is
hard to control the aspect ratio of the final layout. Phase (ii) requires an acyclic
graph as input and the height of the produced layering inherently depends on its

(a) Classic: 0 reversed arcs, (b) CGL: 3 reversed arcs,
20 dummy vertices
44 dummy vertices

(c) MML: 3 reversed arcs,
37 dummy vertices

Fig. 1. (a) A graph drawn with traditional methods [2,4] where every arc has to point
downwards, resulting in a poor aspect ratio – here emphasized by scaling down the
image to fit with the right ones. The methods CGL and MML, presented in this paper,
are able to impose a bound on the height of the drawing, allowing some arcs to point
upwards. The created drawings (b) and (c) are significantly more compact and improve
readability. Reversed arcs are drawn bold and dashed.

longest path. So if phase (i) breaks cycles inappropriately or if an acyclic graph
whose longest path is much larger than its width is already given as initial input,
it is impossible to construct a compact layering. However, the readability and
compactness of a drawing might be considerably improved if arcs to be reversed
are chosen carefully and in an integrated fashion, see Fig. 1 for an example. If
it is required that all arcs point downward, then the layering will have a poor
aspect ratio as shown in Fig. 1a. If we allow reversing some arcs so that they
point upward, the aspect ratio can be improved drastically (see Fig. 1b and 1c).
In order to achieve this, Rüegg et al. [9] suggested to investigate the Generalized Layering Problem (GLP) that combines the first two interdependent phases
of the Sugiyama approach. As the problem is NP-hard, they proposed an integer
linear programming (ILP) formulation in which the weighted sum of the number
of reversed arcs and the arcs lengths is minimized, and where also the height of
the drawing can be restricted. Their approach improved the compactness of the
derived layouts. However, it permits only limited control over the width since it
does not take the dummy vertices into account that are caused by arcs connecting vertices on non-adjacent layers. On the other hand, Healy and Nikolov [5]
have considered the layering problem with dummy vertices, but only for acyclic
directed graphs (DAGs) and for the case that both the desired maximum height
and the width of the drawing are given as inputs.
Contributions. The purpose of this paper is to close this gap, i.e., to derive a
model which is capable of computing a layering of a general digraph by minimizing a weighted sum of the number of reversed arcs, the total arc length, and the
width W of the resulting drawing taking the dummy vertices into account. We
call this the Compact Generalized Layering Problem (CGLP). The only input to
2

our approach, besides the graph and the weights for the objective function, is
the desired maximum height H of the drawing. We will discuss how H can be
chosen such that the existence of a feasible layering is always guaranteed by our
model — which is in contrast to a setting where the user has to specify both H
and W . Nevertheless, an upper bound on W can still be specified.
We present two mixed integer linear programming (MIP) formulations for
the CGLP. The first one (EXT) is a natural extension of the already mentioned
model by Healy and Nikolov for DAGs, and based on assignment variables. The
second one (CGL) is a completely new formulation based on partial orderings.
Our computational experiments on two benchmark sets show that the CGL formulation can be solved much faster than EXT when using a standard commercial
MIP solver (Gurobi1 ) for both of the models. Moreover, CGL is able to compute
optimal solutions for each of the tested problem instances in less than seven
minutes of computation time on a standard PC while taking only a few seconds
for most of them.
While in general we try to keep edges short, we may want to emphasize
reversed arcs, for example in a flow diagram with cycles, by drawing them rather
long; see also Fig. 1c. For this reason, we propose a variant of CGL, called
MML (Min+Max Length), for the problem of minimizing the weighted sum of
reversed arcs, positive forward arc lengths, negative backward arc lengths, and
the maximum number of real vertices on a layer. Within our experiments, MML
is faster than both EXT and CGL without considerably increasing the average
arc lengths and widths of the layouts.
As mentioned by Rüegg et al., the aspect ratio of a final drawing (i. e. in
pixels) does not only depend on the layering but also on the final phases of the
Sugiyama approach, i. e. coordinate assignment and arc routing. Even more, it
can deviate significantly from the aspect ratio estimated after the layering phase,
as described in [9]. Hence, in practice, there is a high demand for methods that
can be quickly adjusted to the specific graph instance and use case. Here, the
models presented in this paper provide more control over the produced layering
compared to existing approaches to the GLP.
Outline. The paper is organized as follows. First, we discuss related research
in Sec. 2. Definitions, preliminaries and motivations for our studies and models
are given in Sec. 3. Sec. 4 presents our newly developed MIP models which are
finally evaluated experimentally in Sec. 5. We conclude with Sec. 6.

2

Related Work

Over the years several approaches have been proposed for the layering phase of
the Sugiyama approach. Eades and Sugiyama proposed a method that is known
as longest path layering [3]. This approach guarantees to produce a layering with
a minimum number of layers, i. e. minimum height, but the width can become
arbitrarily large. Gansner et al. [4] use an ILP formulation to create layerings
1

http://www.gurobi.com/

3

with minimum total arc length that can be solved efficiently using a network
simplex algorithm. The Coffman-Graham algorithm [1] delivers approximate solutions to the precedence-constrained multi-processor scheduling problem that
can be used to calculate a layering with a maximum number of real vertices per
layer. However, dummy vertices are not taken into account but can have a significant impact on the actual width of the drawing. Still, Nachmanson et al. [7]
use the Coffman-Graham algorithm as part of an iterative heuristic procedure
to produce drawings with a certain aspect ratio.
The layering problem with restricted width and consideration of dummy
vertices has been studied in the literature as well. Healy and Nikolov found that
minimizing the number of dummy vertices during layering inherently produces
compact drawings [6]. Following this observation, they target dummy vertex
minimization with a branch and cut algorithm that is able to incorporate bounds
on both width and height [5]. Nikolov et al. discuss heuristics to find layerings
with small width when considering dummy vertices [8], however, no explicit
bound on the width and height can be used.
Since all of the above methods rely on the input graph to be acyclic, the
minimum height of their layerings directly relates to the longest path of the
graph. Rüegg et al. [9] integrate the first two phases of the Sugiyama approach
to allow arbitrary graphs as input by minimizing a weighted sum of the number
of reversed arcs and the number of dummy vertices. They showed that this
overcomes the previously mentioned problem regarding a graph’s longest path
and also allows more compact drawings in general. Still, they did not consider
hard bounds on the width and height of the drawing and did not consider the
contribution of dummy vertices to the width.

3

Preliminaries

As we are concerned with the layering phase of the layout method suggested by
Sugiyama et al. [10], we briefly recall the definition of layerings of directed graphs
at the beginning of this section. Afterwards, we state our new layering problem
definition and discuss how to guarantee the existence of feasible drawings under
this model.
Layerings of directed graphs. A layering of a directed graph G = (V, A) with
vertex set V and arc set A is a function ` : V → N+ assigning a layer `(v) to
each vertex v ∈ V . In our context, for a feasible layering, it is necessary that
no two adjacent vertices are placed on the same layer, i.e., `(u) 6= `(v) for all
(u, v) ∈ A. The layering determines the height, the width, the arc lengths, and
the number of reversed arcs, which will be defined in the following. The height H
of a layering ` is the maximum layer used by `. The width Wk (`) of a layer k in a
layering ` is the sum of the number of vertices assigned to layer k and the number
of dummy vertices caused by arcs traversing the layer k. More formally, let
Vk = {v ∈ V | `(v) = k} and Dk = {(u, v) ∈ A | `(u) < k and `(v) > k or `(v) <
k and `(u) > k}. Then Wk (`) = |Vk | + |Dk | and the width of ` is defined as
4

the maximum width of all layers in `, i.e., W = max1≤k≤H Wk (`). The total arc
length len(`) is the sum of the arc lengths |`(u) − `(v)| of all arcs (u, v) ∈ A
in the layering `. An arc (u, v) ∈ A in a layering ` is called a reverse arc if
`(u) > `(v) and the total number of reversed arcs in ` is denoted by rev(`). The
estimated aspect ratio of a layering with width W and height H is defined as
W/H. In contrast, the aspect ratio, considers the width and height of a final
layout after all of the Sugiyama phases. So far, we assumed that real as well as
dummy vertices have unit width. Nevertheless, each of our MIP models presented
in Sec. 4 can easily be extended to deal with varying vertex widths.
Asking the user to specify bounds on both the height H and the width W
of a hierarchical drawing a priori can easily lead to infeasible problem settings
or require several iterations to fit the parameters to the graph structure. We
circumvent these issues in our subsequently defined variation of the problem by
requiring only H as an input parameter while making W a subject of optimization. We also discuss how H can be chosen safely.
The Compact Generalized Layering Problem (CGLP). As an extension to the
Generalized Layering Problem (GLP) described in [9], we define the Compact
Generalized Layering Problem as follows: Given a (not necessarily acyclic) directed graph G = (V, A) and a maximum layering height H, compute a layering `
such that the end-vertices of each arc are assigned to different layers and the
following objective function is minimized: the weighted sum of the number of
reversed arcs rev(`), the total arc length len(`), and the width W (`).
Lower Bounds on the height H of feasible layerings. Since, in our generalized
setting, the direction of the arcs can be arbitrary, we can think of undirected
graphs to determine a lower bound on H. To assign layers to vertices such that no
two adjacent vertices are on the same layer is an equivalent problem as to assign
colors to vertices such that no two adjacent vertices have the same color. Hence,
the minimum number of layers, i.e., height, necessary for a feasible layering of
an undirected graph G = (V, E) is equal to its chromatic number χ(G).
Since it is NP-hard to compute χ(G), we suggest to approximate it. A valid
upper bound for χ(G) that can be computed in linear time is the maximum
vertex degree maxv∈V deg(v) of G plus one. This bound is tight if G is the complete graph or an odd cycle, otherwise χ(G) ≤ maxv∈V deg(v) for any connected
graph G. A better approximation can be achieved by using the largest eigenvalue
λ∗ of the adjacency matrix of G. Wilf showed that χ(G) ≤ 1+λ∗ [11] and together
|E|
∗
with the Perron-Frobenius Theorem we have that 2 |V
| ≤ λ ≤ maxv∈V deg(v).
Summing up, we have H ≥ χ(G) ≤ λ∗ + 1 ≤ maxv∈V deg(v) + 1.

4
4.1

Description of the MIP Models
A Generalization of the Model by Healy and Nikolov (EXT)

As a reference, we consider a natural extension of the model by Healy and
Nikolov [5] that minimizes the total arc length of layered drawings of acyclic
5

digraphs while restricting the height as well as the width and taking dummy vertices into account. In their model, the height H and the width W are fixed input
parameters. In our extension for general digraphs G = (V, A), we only require
H as an input, and incorporate the width of the drawing into the optimization
process. The model describes an assignment problem (AP) with variables xv,k
to decide whether vertex v ∈ V is placed on layer 1 ≤ k ≤ H (xv,k = 1) or not
(xv,k = 0). If an arc (u, v) ∈ A is reversed, then this is expressed by a variable
ru,v = 1, otherwise ru,v = 0. The variables zuv,k model whether arc (u, v) causes
a dummy vertex on layer 2 ≤ k ≤ H − 1, which is important to formulate a
proper width constraint. To save extra arc length variables, we exploit the fact
that the length of an arc is exactly the number of dummy vertices it causes plus
one. The full model is:

ru,v + ωlen

P

min ωrev
H
P

H−1
P


zuv,k + ωwid W

(u,v)∈A k=2

(u,v)∈A

s.t.

P

xv,k

=1

for all v ∈ V

(1)

xu,k + xv,k

≤1

for all (u, v) ∈ A, 1 ≤ k ≤ H

(2)

≤ ruv

for all (u, v) ∈ A, 1 ≤ k ≤ H

(3)

≤W

for all k ∈ {1, H}

(4)

≤W

for all 2 ≤ k ≤ H − 1

(5)

xu,l

≤ zuv,k

for all (u, v) ∈ A, 2 ≤ k ≤ H − 1

(6)

xv,l

≤ zuv,k

for all (u, v) ∈ A, 2 ≤ k ≤ H − 1

(7)

xv,k

∈ {0, 1}

for all v ∈ V, 1 ≤ k ≤ H

ru,v

∈ [0, 1]

for all (u, v) ∈ A

zuv,k

∈ [0, 1]

for all (u, v) ∈ A, 2 ≤ k ≤ H − 1

W

∈ R≥0

k=1

xu,k −

H
P

xv,l

l=k

P

xv,k

v∈V

P

xv,k +

P

xv,l −

l<k

P

P

zuv,k
(u,v)∈A

v∈V

P
l≤k

xu,l −

l<k

P
l≤k

The objective function minimizes the weighted sum of the number of reversed
arcs, the total arc length, and the width W of the drawing. Equations (1) ensure
that exactly one layer is assigned to each v ∈ V . Inequalities (2) enforce adjacent
vertices to be placed on different layers. If an arc (u, v) is reversed due to the
positions of its end vertices, then inequality (3) makes sure that ru,v is equal to
1 (otherwise, it will be 0 due to the objective function). The total number of
vertices and dummy vertices assigned to one layer must never exceed W which is
ensured by (4) and (5). Finally, inequalities (6) and (7) enforce a variable zuv,k
to be 1 if `(u) < k and `(v) > k or vice versa. The integrality of all continuous
variables is implied by the integrality of the x-variables due to the constraints
and the objective function. Model EXT has O(|V | · H + |A| · H) variables and
O(|V | + |A| · H) constraints.
6

4.2

Our New Ordering-Based MIP Model (CGL)

The CGL model is based on the observation that the layering problem is a
partial ordering problem (POP) in the sense that a vertex u is smaller than v
(i.e., u < v) in the partial order if `(u) < `(v).
Following this idea, we introduce, for each v ∈ V and for each 1 ≤ k ≤ H,
the variables yv,k that are equal to 1 if and only if `(v) < k. Conceptually, we
also have the reverse variables yk,v (equal to 1 if and only if k < `(v)), but we
will see soon that these can be discarded. However, with the reverse variables at
hand, it is easy to see that `(v) = k if and only if yk,v = yv,k = 0. In addition,
the new model also comprises the variables ru,v and zuv,k as already introduced
in Sec. 4.1. The interplay between the y- and the r-variables as described in the
following will lead to the desired partial ordering of V . The full model is:

min ωrev

P


ru,v + ωlen

(u,v)∈A

P

H−1
P


zuv,k + ωwid W

(u,v)∈A k=2

s.t. yv,1

=0

for all v ∈ V

(8)

yH,v

=0

for all v ∈ V

(9)

yk,v + yv,k+1

=1

for all v ∈ V, 1 ≤ k ≤ H − 1

(10)

yk+1,v − yk,v

≤0

for all v ∈ V, 1 ≤ k ≤ H − 2

(11)

−yu,k − yk,v − ru,v

≤ −1

for all (u, v) ∈ A, 1 ≤ k ≤ H

(12)

−yk,u − yv,k + ru,v

≤0

for all (u, v) ∈ A, 1 ≤ k ≤ H

(13)

yk,u + yv,k − zuv,k

≤1

for all (u, v) ∈ A, 2 ≤ k ≤ H − 1 (14)

yk,v + yu,k − zuv,k
P
(1 − yu,k − yk,u )

≤1

for all (u, v) ∈ A, 2 ≤ k ≤ H − 1 (15)

≤W

for all k ∈ {1, H}

(16)

≤W

for all 2 ≤ k ≤ H − 1

(17)

yv,k , yk,v

∈ {0, 1}

for all v ∈ V, 1 ≤ k ≤ H

u∈V

P
P
(1 − yu,k − yk,u ) + zuv,k
u∈V

(u,v)∈A

ru,v

∈ [0, 1]

for all (u, v) ∈ A

zuv,k

∈ [0, 1]

for all (u, v) ∈ A, 2 ≤ k ≤ H − 1

W

∈ R≥0

The switch from an AP to a POP requires a more involved approach to yield
consistency of the model. The first four constraints enforce the graph to be
embedded into the layers 1, . . . , H. Equations (8) and (9) make sure no vertex
is assigned a layer smaller than one or larger than H. For each layer 1 ≤ k ≤ H,
each vertex v is either assigned a layer larger than k (in which case yk,v = 1) or
not (in which case yv,k+1 = 1) as is enforced by (10). These equations can be
used to eliminate one half of the y-variables (and then be eliminated themselves)
as mentioned before. If `(v) > k + 1, then this implies `(v) > k as well and this
is expressed in the transitivity inequalities (11). It remains to show that arc
directions and layer assignments will be consistent and no two adjacent vertices
7

can be on the same layer. This is achieved by inequalities (12) and (13). Suppose
that ru,v = 0, i.e., the arc (u, v) ∈ A shall be a forward arc. Then the inequalities
(12) enforce that, for each layer 1 ≤ k ≤ H, either `(u) < k or `(v) > k (or both).
In this case, the inequalities (13) are inactive, but they take the equivalent role
in the reversed-arc case where ru,v = 1 and then inequalities (12) are inactive.
As already discussed for the previous model, a dummy vertex on layer k is
caused by arc (u, v) ∈ A if either `(u) > k and `(v) < k (yk,u + yv,k − 1 = 1), or
vice versa (yk,v + yu,k − 1 = 1). In the first case, inequality (14) will force zuv,k
to be 1, in the second case, inequality (15) will do so. In any other case, the
variable will be zero due to the objective function. Finally, inequalities (16) and
(17) count the vertices and dummy vertices placed on each layer k and make
sure that W is a proper upper bound on the width of the layering. The CGL
formulation has O(|V | · H + |A| · H) variables and constraints.
4.3

A Min+Max Length Variant Without Dummy Vertices (MML)

We shortly describe a variant of CGL, called MML, that can produce appealing
results usually faster when dummy vertices need not be taken into account in
terms of the width. As opposed to W , let Wr be the width of a layering where
only the real vertices are counted.
The idea is to remove the dummy vertex variables zuv,k together with the
constraints (14), (15) and to replace inequalities (16) and (17) simply by:
P
(1 − yu,k − yk,u )

≤ Wr

for all 1 ≤ k ≤ H

u∈V

We now need to count arc lengths in an ordinary fashion. The usual way to
do this is to introduce length variables lu,v ∈ R and the following two inequalities
per arc in order to capture the absolute length depending on the arc direction.
H
P

(yk,v − yk,u )

≤ lu,v

for all (u, v) ∈ A

(18)

≤ lu,v

for all (u, v) ∈ A

(19)

k=1
H
P

(yk,u − yk,v )

k=1

However, for certain use cases, e. g., when feedback should be emphasized,
it can be desirable to draw forward arcs as short as possible and maximize the
length of the reversed arcs. Therefore, we propose not to introduce the l-variables
but to directly incorporate the terms used on the left hand side of inequalities (18) into the objective function, which results in the desired minimization
of the backward arcs’ negative lengths. MML’s objective function is:
min ωrev

P
(u,v)∈A


ru,v + ωlen

P

H
P


(yk,v − yk,u ) + ωwid Wr

(u,v)∈A k=1

This model has only O(|V | · H + |A|) variables and O(|V | · H + |A| · H)
constraints.
8

5

Evaluation

Setup. The experiments were performed single-threadedly on an Intel Core i74790, 3.6 GHz, with 32 GB of memory and running Ubuntu Linux 14.04. For
solving the MIPs, we used Gurobi 6.5. In our implementation, the CGL model
has been reduced in terms of its variables as is indicated in Sec. 4.2. Further, in all
the models we enforce at least one vertex to be placed on layer
p k = 1 to eliminate
some symmetries. The parameters were set to H = d1.6 ∗ |V |e, wrev = |E| · H,
wlen = 1, and wwid = 1. This choice of H delivered feasible problems for all
of our instances and emphasizes our target to have a good aspect ratio and a
drawing that adheres to standard forms such as flat screens following the golden
ratio. Due to our choice of wrev , arcs are reversed only if this is unavoidable due
to the specified height or because they are part of a cycle.
We are interested in answering the following questions:
(H1) Does the POP-oriented CGL model dominate the AP-based EXT model in
terms of running times?
(H2) Is MML a good alternative concerning the running times and the metrics
(arc length, W , and estimated aspect ratio) of the generated layerings?
(H3) How do CGL and MML influence the aspect ratio of the final drawings?
We used two benchmark sets2 . The first set ATTar, the same as used by
Rüegg et al. [9], is an extraction of 146 acyclic AT&T graphs with at least
20 vertices having aspect ratio smaller than 0.5 when drawn with the classic
Sugiyama approach. These graphs have between 20 and 99 vertices and between
20 and 168 arcs. Their arc to vertex density is about 1.5 on average but varies
significantly. Especially, the density of some graphs with about 60 vertices is up
to 4.7 which is why the results displayed in our figures and boxplots stand out
for these instances.
The second benchmark set Random consists of 340 randomly generated, not
necessarily acyclic graphs with 17 to 100 vertices, 30 to 158 arcs, and 1.5 arcs
per vertex. We used these graphs in order to analyze our approach also for cyclic
sparse digraphs. First, a number of vertices was created. Afterwards, for each
vertex, a random number of outgoing arcs (with arbitrary target) is created such
that the overall number of arcs is 1.5 times the number of vertices.
(H1): Comparison of CGL and EXT. First, we look at the ATTar instances
and model EXT. While small instances with up to 25 vertices can be solved
within at most seven seconds, there is already one instance with 29 vertices
that cannot be solved within the time limit of 10 minutes of CPU and system
time. In total, eleven of 66 instances with 25 < |V | < 50 time out, while for
the others the running times highly deviate within the full spectrum between a
second and about nine minutes. However, none of the 33 instances with more
than 50 vertices can be solved within the time limit. The picture for the random
2

Both benchmark sets are available on https://ls11-www.cs.tu-dortmund.de/
mutzel/gdbenchmarks

9

[75, 90)

[90, 105)

[75, 90)

[90, 105)

[45, 60)

[30, 45)

[15, 30)

(b) Arc Lengths

5

35

(c) Width W

2.0
1.5
[60, 75)

1.0
[45, 60)

[30, 45)

[15, 30)

1
[90, 105)

[75, 90)

[60, 75)

[45, 60)

[30, 45)

[15, 30)

10

15

2

20

3

25

30

4

40

2.5

50

(a) Execution Time [s]

[60, 75)

150

50
[90, 105)

[75, 90)

[60, 75)

[45, 60)

[30, 45)

[15, 30)

0

0

5

2

150

15

250

250

25

350

350

8
4

6

CGL
MML

(d) Estimated Aspect Ratio W/H

Fig. 2. Summary of the results of the ATTar graphs. For each of the four metrics the
graphs were binned based on their vertex counts (x axis) and the y axis represents
the metric’s value. For each bin the left box represents CGL’s result and the right box
MML’s result.

instances is similar. The first instance remaining unsolved within the time limit
has 37 vertices and those with 50 or more vertices can be solved only sporadically
(33 of 201).
With the CGL model, however, we were able to solve all the instances (ATTar and Random) to optimality. The running times are shown in Fig. 2a and 3a.
All but ten of the ATTar instances were solved in less than 10 seconds of CPU
and system time, and the highest running time observed was 30 seconds. Concerning the random instances, we observed that 314 of the 340 instances were
solved within 30 seconds. However, for |V | ≥ 80, a higher dispersion of running
times could be observed. The largest observed running time was 388 seconds
for an instance with 92 vertices. Since both models solve the same problem to
optimality, we can conclude that the EXT model is clearly dominated by the
CGL model when a state-of-the-art commercial MIP solver is used.
10

350

250

250

250

[75, 90)

[90, 105)

[75, 90)

[90, 105)

[60, 75)

[45, 60)

(b) Arc Lengths

2.5

2.4
2.0

2.0
[45, 60)

[30, 45)

[15, 30)

(c) Width W

[60, 75)

1.6

1.5
1.0
[90, 105)

[75, 90)

[60, 75)

[45, 60)

[30, 45)

[15, 30)

20

10

25

15

30

20

35

25

40

30

2.8

(a) Execution Time [s]

[30, 45)

[15, 30)

150

50
[90, 105)

[75, 90)

[60, 75)

[45, 60)

[30, 45)

[15, 30)

0

0

50

5

150

10

150

15

CGL
MML

(d) Estimated Aspect Ratio W/H

Fig. 3. Summary of the results of the random graphs. For each of the four metrics,
the graphs were binned based on their vertex counts (x axis) and the y axis represents
the metric’s value. For each bin, the left box represents CGL’s result and the right box
MML’s result. To improve presentation, we removed one outlier in (a) with 92 vertices
that took CGL 388s of computation time.

(H2): Alternative MML. In Sec. 4.3 we introduced the model MML that, as
opposed to the models EXT and CGL, maximizes the length of reversed arcs
and does not regard the contribution of dummy vertices to a layer’s width. Our
hope was that MML is much faster than CGL and EXT without sacrificing the
quality of the generated layouts too much.
In Fig. 2a and 3a, one can see that the MML model could almost always
(except for 14 instances in total) be solved much faster than the CGL model
and hence also the EXT model. Especially, with MML all but ten instances of
the ATTar benchmark set were solved within three seconds. The boxplots also
show that the running times for solving the MML model are more robust for
both benchmark sets.
As can be seen in Fig. 2 and 3, the average arc lengths and widths of layerings
created by MML increase only moderately when compared to CGL. On average,
the increase in the total arc lengths is only about 6% and the increase in the
11

0.8

6
5

0.6

4

0.4

3

0.2

2

0.0

1
0
Classic

CGL

MML

Classic

(a) Estimated Aspect Ratio (W/H)

CGL

MML

(b) Aspect Ratio of Final Drawing

Fig. 4. Comparison of the aspect ratio of the ATTar instances when laid out with traditional methods [2,4] (box on the left), CGL (middle), and MML (right). It can be seen
that the methods presented here clearly improve the aspect ratio of the final drawing.

width is about 7% for each of the benchmark sets. The displayed widths of MML
also include dummy vertices. Since MML is significantly faster than CGL, we
can conclude that it is a good alternative to CGL whenever lower running times
are required and long reversed arcs are either desired or negligible.
(H3): Aspect Ratio. Exemplary drawings of both CGL and MML can be seen
in Fig. 1 and Fig. 5. Both show layouts of ATTar instances. Whereas the aspect
ratio of the original layout of Fig. 1 is about 0.14, the ratio of the new layouts is
about 0.6. This improvement of the aspect ratio has been achieved by reversing
three arcs (now pointing upwards). The created drawings are significantly more
compact. In Fig. 1c, generated with the MML model, the reversed arcs can be
found easily, since the model tries to maximize their length.
An average of about 3.13 arcs needed to be reversed on the ATTar graphs
and 3.82 on the random graphs to adhere to the selected H. Also the maximum
number of reversed arcs in both benchmark sets is similar; it is 8 for the ATTar
instances and 9 for the random instances. The reversed arcs changed the estimated aspect ratio of the ATTar graphs from an average of 0.51 to an average
of 1.36, see Fig. 4a. As mentioned earlier, the estimated aspect ratio must not
necessarily coincide with the final drawing’s aspect ratio. To further inspect this,
we produced final drawings using the same strategies of the Sugiyama approach
as discussed in [9]. In Fig. 4b, one can see that the average aspect ratio improves
from 0.22 to about 0.61 for CGL and to about 0.63 for MML. From this we
conclude that both models lead to compact layouts with improved aspect ratio.

6

Conclusion

This paper introduces the CGLP, which can be seen as an extension of the DAG
Layering Problem suggested by Healy and Nikolov [5,6], and the GLP suggested
12

by Rüegg et al. [9]. The CGLP gives more control over the desired layering by
integrating the reversal of arcs and taking the contribution of dummy vertices
to a layering’s width into account.
We suggest two MIP models for CGLP, one of which is based on partial
orderings and show that the model can be solved to optimality within a short
computation time for typical instances with up to 100 vertices. In addition, we
suggest an alternative MIP model (MML) for a slightly different problem which
can be solved even faster while the widths and arc lengths of the generated layerings do not increase significantly. Our experiments have shown that using the
CGLP, indeed, the aspect ratio of the generated final drawings can be influenced.
Acknowledgements. This work was supported by the German Research Foundation under the project Compact Graph Drawing with Port Constraints (ComDraPor, DFG HA 4407/8-1 and MU 1129/9-1).

References
1. E. G. Coffman. and R. L. Graham. Optimal scheduling for two-processor systems.
Acta Informatica, 1(3):200–213, 1972.
2. P. Eades, X. Lin, and W. F. Smyth. A fast and effective heuristic for the feedback
arc set problem. Information Processing Letters, 47(6):319–323, 1993.
3. P. Eades and K. Sugiyama. How to draw a directed graph. Journal of Information
Processing, 13(4):424–437, 1990.
4. E. R. Gansner, E. Koutsofios, S. C. North, and K.-P. Vo. A technique for drawing
directed graphs. Software Engineering, 19(3):214–230, 1993.
5. P. Healy and N. S. Nikolov. A branch-and-cut approach to the directed acyclic
graph layering problem. In Proceedings of the 10th International Symposium on
Graph Drawing (GD’02), volume 2528 of LNCS, pages 98–109. Springer, 2002.
6. P. Healy and N. S. Nikolov. How to layer a directed acyclic graph. In Proceedings
of the 9th International Symposium on Graph Drawing (GD’01), volume 2265 of
LNCS, pages 563–566. Springer, 2002.
7. L. Nachmanson, G. Robertson, and B. Lee. Drawing graphs with GLEE. In S.-H.
Hong, T. Nishizeki, and W. Quan, editors, Graph Drawing, volume 4875 of LNCS,
pages 389–394. Springer Berlin Heidelberg, 2008.
8. N. S. Nikolov, A. Tarassov, and J. Branke. In search for efficient heuristics for
minimum-width graph layering with consideration of dummy nodes. Journal of
Experimental Algorithmics, 10, 2005.
9. U. Rüegg, T. Ehlers, M. Spönemann, and R. von Hanxleden. A generalization
of the directed graph layering problem. In Proceedings of the 24th International
Symposium on Graph Drawing and Network Visualization (GD’16), 2016.
10. K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. IEEE Transactions on Systems, Man and Cybernetics,
11(2):109–125, Feb. 1981.
11. H. S. Wilf. The eigenvalues of a graph and its chromatic number. Journal London
Math. Soc., 42:330–332, 1967.

13

A
A.1

Appendix
Additional Experimental Results

Example Layout of an AT&T Instance Fig. 5 shows an instance of the
ATTar benchmark set with 48 vertices drawn with the standard layering method
[2,4]. If it is required that all arcs point downward, then the layering will have a
poor aspect ratio as shown in Fig. 5a. If we allow to reverse only two arcs, the
aspect ratio can be improved tremendously (see Fig. 5b and 5c). The methods
CGL and MML, presented in this paper, are able to respect a bound on the
height of the drawing, allowing a number of arcs to point upwards. The created
drawings are also significantly more compact. The reversed arcs in (b) and (c)
are drawn bold and dashed.

(b) CGL: 2 reversed arcs,
(a) Classic: 0 reversed arcs, 29 dummy vertices
62 dummy vertices

(c) MML: 2 reversed arcs,
34 dummy vertices

Fig. 5. (a) Layout with existing methods where every arc has to point downwards.
(b) Layout with solution of model CGL (c) Layout with solution of model MML. The
reversed arcs in (b) and (c) are drawn bold and dashed.

More Results of the CGL and MML Models Tables 1 and 2 show the
results for the benchmark sets ATTar and Random. In both tables, I denotes
the number of instances for the given vertex count range. n̄ and ē are the average
number of vertices and arcs. W is the average width, i. e., the maximum number
of vertices per layer including dummy vertices. For each drawing, the height
was fixed as discussed in the paper. EL and RE denote the average arc lengths
and number of reversed arcs. Standard deviations are given in brackets. A good
overview over the distribution of the runtimes across the instances can also be
obtained from Fig. 6 and Fig. 7.
14

Node Counts

I

n̄

ē

W

[15, 30)

53

22.7

[2.1]

33.3

[16.4]

CGL
MML

9.6
10.6

[6.8]

[30, 45)

44

38.0

[5.1]

52.8

[10.8]

CGL
MML

12.2
13.4

[4.6]

[45, 60)

29

50.5

[4.1]

80.8

[26.9]

CGL
MML

17.1
18.2

[7.4]

[60, 75)

12

62.8

[2.6]

112.6

[12.0]

CGL
MML

30.2
30.5

[7.2]

[75, 90)

4

81.2

[4.9]

117.0

[15.8]

CGL
MML

21.2
24.2

[5.1]

[90, 105)

4

94.8

[3.7]

139.5

[15.1]

CGL
MML

22.2
27.2

[9.5]

[6.5]

[4.3]

[7.7]

[6.8]

[6.5]

[9.8]

EL
52.6
57.5

[46.7]

88.1
96.2

[29.6]

155.2
162.5

[68.8]

254.8
265.0

[48.4]

221.0
249.2

[26.4]

272.8
296.2

[60.8]

[46.8]

[30.8]

[68.5]

[49.1]

[37.7]

[78.3]

RE
2.1
2.1

[1.3]

2.9
2.9

[1.3]

3.8
3.8

[1.5]

5.7
5.7

[1.2]

5.2
5.2

[1.7]

5.5
5.5

[0.6]

[1.3]

[1.3]

[1.5]

[1.2]

[1.7]

[0.6]

Table 1. Summary table for the set of ATTar graphs. Notations are defined above.

Node Counts

I

n̄

ē

W

[15, 30)

54

23.3

[3.7]

36.9

[6.0]

CGL
MML

11.9
12.6

[2.1]

[30, 45)

65

37.2

[4.3]

59.0

[7.6]

CGL
MML

16.5
17.7

[2.8]

[45, 60)

62

52.4

[4.3]

82.9

[7.1]

CGL
MML

22.0
23.1

[3.0]

[60, 75)

60

66.7

[3.9]

105.9

[7.0]

CGL
MML

26.7
27.8

[3.8]

[75, 90)

63

81.6

[4.2]

128.7

[7.5]

CGL
MML

31.4
32.6

[4.0]

[90, 105)

36

94.6

[3.3]

147.9

[5.1]

CGL
MML

34.1
35.9

[3.2]

[2.1]

[3.1]

[3.1]

[3.6]

[4.2]

[3.4]

EL
61.4
65.7

[13.3]

105.3
111.0

[22.1]

159.8
167.4

[29.0]

216.3
223.8

[32.4]

277.3
286.1

[32.8]

316.9
325.3

[36.3]

[12.7]

[19.7]

[27.1]

[31.8]

[31.7]

[38.5]

RE
2.5
2.5

[1.1]
[1.1]

3.0
3.0

[1.4]

4.0
4.0

[1.6]

4.4
4.4

[1.5]

4.4
4.4

[1.6]

5.2
5.2

[1.7]

[1.4]

[1.6]

[1.5]

[1.6]

[1.7]

Table 2. Summary table for the set of random graphs. Notations are defined above.

15

35

MML
CGL

30

Time [s]

25
20
15
10
5
0

20

30

40

50

60 70 80
Vertices
(a) Execution Time

90 100

60

400

MML
CGL

350

MML
CGL

50

300

40

200

W

Arc length

250

150

30
20

100

10

50
0

20

30

40

50

60 70
Vertices

80

0

90 100

(b) Arc Length

20

30

40

50

60 70
Vertices
(c) W

80

90 100

Fig. 6. Results for the models CGL and MML for the ATTar graphs. Values for instances with the same number of vertices are averaged.

16

100

MML
CGL

80

Time [s]

60
40
20
0

20

40

60
Vertices

80

100

(a) Execution Time
40

400

MML
CGL

350
300

30
25

200

W

Arc length

250

20

150

15

100

10

50
0

MML
CGL

35

20

40

60
Vertices

80

5

100

(b) Arc Length

20

40

60
Vertices
(c) W

80

100

Fig. 7. Results for the models CGL and MML for the random graphs. Values for
instances with the same number of vertices are averaged.

17

