---
abstract: |
    The solves a step of the widely used layer-based approach to automatically draw directed acyclic graphs. To cater for cyclic graphs, usually a preprocessing step is used that solves the to make the graph acyclic before a layering is determined.

    Here we present the , which solves the combination of and simultaneously, allowing general graphs as input. We present an integer programming model and a heuristic to solve the and perform thorough evaluations on different sets of graphs and with different implementations for the steps of the layer-based approach.

    We observe that reduces the number of dummy nodes significantly, can produce more compact drawings, and improves on graphs where yields poor aspect ratios.

    layer-based layout, layer assignment, linear arrangement, feedback arc set, integer programming
author:
- Ulf Rüegg
- Thorsten Ehlers
- |
    \
    Miro Sp[ö]{}nemann
- Reinhard von Hanxleden
bibliography:
- 'cau-rt.bib'
- 'rts-arbeiten.bib'
- 'pub-rts.bib'
title: |
    A Generalization of the\
    Directed Graph Layering Problem
---

Introduction {#sec:introduction}
============

The layer-based approach is a well-established and widely used method to automatically draw directed graphs. It is based on the idea to assign nodes to subsequent *layers* that show the inherent direction of the graph, see for an example. The approach was introduced by Sugiyama  [@SugiyamaTT81] and remains a subject of ongoing research.

Given a directed graph, the layer-based approach was originally defined for acyclic graphs as a pipeline of three phases. However, two additional phases are necessary to allow practical usage, which are marked with asterisks:

1.  *Cycle removal\*:* Eliminate all cycles by reversing a preferably small subset of the graph’s edges. This phase adds support for cyclic graphs as input.

2.  *Layer assignment:* Assign all nodes to numbered *layers* such that edges point from layers of lower index to layers of higher index. Edges connecting nodes that are not on consecutive layers are split by so-called *dummy nodes*.

3.  *Crossing reduction:* Find an ordering of the nodes within each layer such that the number of crossings is minimized.

4.  *Coordinate assignment:* Determine explicit node coordinates with the goal to minimize the distance of edge endpoints.

5.  *Edge routing\*:* Compute bend points for edges, with an orthogonal style.

While state-of-the-art methods produce drawings that are often satisfying, there are graph instances where the results show bad *compactness* and unfavorable *aspect ratio* [@GutwengervHM+14]. In particular, the number of layers is bound from below by the longest path of the input graph after the first phase. When placing the layers vertically one above the other, this affects the height of the drawing, see . Following these observations, we present new methods to overcome current limitations.

#### Contributions.

[R]{}[.5]{}

\

The focus of this paper is on the first two phases stated above. They determine the initial topology of the drawing and thus directly impact the compactness and the aspect ratio of the drawing.

We introduce a new layer assignment method which is able to handle cyclic graphs and to consider compactness properties for selecting an edge reversal set. Specifically, 1) it can overcome the previously mentioned lower bound on the number of layers arising from the longest path of a graph, 2) it can be flexibly configured to either favor elongated or narrow drawings, thus improving on aspect ratio, and 3) compared to previous methods it is able to reduce both the number of dummy nodes and reversed edges for certain graphs. See and for examples.

We discuss how to solve the new method to optimality using an integer programming model as well as heuristically, and evaluate both.

#### Outline.

The next section presents related work. We introduce problems and definitions in , and present methods to solve the newly introduced problems in and . discusses thorough evaluations before we conclude in .

Related Work {#sec:related_work}
============

The cycle removal phase targets the . Several approaches have been proposed to solve either to optimality or heuristically [@HealyN13]. In the context of layered graph drawing, reversing a minimal number of edges does not necessarily yield the best results, and application-inherent information might make certain edges better candidates to be reversed [@GansnerKNV93]. Moreover, the decision which edges to reverse in order to make a graph acyclic has a big impact on the results of the subsequent layering phase. Nevertheless the two phases are executed separately until today.

To solve the second phase, the layer assignment problem, several approaches with different optimization goals have emerged. Eades and Sugyiama employ a longest path layering, which requires linear time, and the resulting number of layers equals the number of nodes of the graph’s longest path [@EadesS90]. Gansner solve the layering phase by minimizing the sum of the edge lengths regarding the number of necessary dummy nodes [@GansnerKNV93]. They show that the problem is solvable in polynomial time and present a network simplex algorithm which in turn is not proven to be polynomial, although it runs fast in practice. This approach was found to inherently produce compact drawings and performed best in comparison to other layering approaches [@HealyN02a].

[r]{}[.5]{}

Healy and Nikolov tackle the problem of finding a layering subject to bounds on the number of layers and the maximum number of nodes in any layer with consideration of dummy nodes using an integer linear programming approach [@HealyN02a]. The problem is , even without considering dummy nodes. In a subsequent paper they present a branch-and-cut algorithm to solve the problem faster and for larger graph instances [@HealyN02b]. Later, Nikolov propose and evaluate several heuristics to find a layering with a restricted number of nodes in each layer [@NikolovTB05]. Nachmanson present an iterative algorithm to produce drawings with an aspect ratio close to a previously specified value [@NachmansonRL08].

All of the previously mentioned layering methods have two major drawbacks. 1) They require the input graph to be acyclic upfront, and 2) they are bound to a minimum number of layers equal to the longest path of the graph. In particular this means that the bound on the number of layers in the methods of Nikolov cannot be smaller than the longest path.

In the context of force-directed layout, Dwyer and Koren presented a method that can incorporate constraints enforcing all directed edges to point in the same direction [@DwyerK05]. They explored the possibility to relax some of the constraints, let some of the edges point backwards, and found that this improves the readability of the drawing. In particular, it reduced the number of edge crossings.

Definitions and Problem Classification {#sec:preliminaries}
======================================

Let $G=(V,E)$ denote a graph with a set of nodes $V$ and a set of edges $E$. We write an edge between nodes $u$ and $v$ as $(u,v)$ if we care about direction, as $\{u,v\}$ otherwise. A *layering* of a directed graph $G$ is a mapping $L: V \rightarrow \mathbb{N}$. A layering $L$ is *valid* if $\forall (u,v) \in E$: $L(v) - L(u) \geq 1$.

Let $G = (V,E)$ be an acyclic directed graph. The problem is to find a minimum $k$ and a valid layering $L$ such that $\sum_{(v,w) \in E} (L(w) - L(v)) = k$.

As mentioned in , was originally introduced by Gansner  [@GansnerKNV93]. We extend the idea of a layering for directed acyclic graphs to general graphs, graphs that are either directed or undirected and that can possibly be cyclic. Undirected graphs can be handled by assigning an arbitrary direction to each edge, thus converting it into a directed one, and by hardly penalizing reversed edges. We call a layering $L$ of a general graph $G$ *feasible* if $\forall \{u,v\} \in E: |L(u) - L(v)| \geq 1$.

Let $G = (V,E)$ be a possibly cyclic directed graph and let $\wlen, \wrev \in \mathbb{N}$ be weighting constants. The problem is to find a minimum $k$ and a feasible layering $L$ such that $$\wlen\left( \sum_{(v,w) \in E} \left|L(w) - L(v)\right| \right)
   + \wrev\left|\left\{ (v,w) \in E: L(v) > L(w) \right\}\right| \ = \ k \enspace.$$

Intuitively, the left part of the sum represents the overall edge length (the number of dummy nodes) and the right part represents the number of reversed edges (the ). After reversing all edges in this , the feasible layering becomes a valid layering. Compared to the standard cycle removal phase combined with , the generalized layering problem allows more flexible decisions on which edges to reverse. Also note that with $\wlen = 1, \wrev = \infty$ is equivalent to for acyclic input graphs and that while is solvable in polynomial time, both parts of are [@RueeggESvH15].

The IP Approach {#sec:glay}
===============

In the following, we describe how to solve using integer programming. The rough idea of this model is to assign integer values to the nodes of the given graph that represents the layer in which a node is to be placed.

*Input and parameters.* Let $G=(V,E)$ be a graph with node set $V = \{1,\dots,n\}$. Let $e$ be the adjacency matrix, $e(u,v) = 1$ if $(u,v) \in E$ and $e(u,v) = 0$ otherwise. $\wlen$ and $\wrev$ are weighting constants.

*Integer decision variables.* $l(v)$ takes a value in $\{1,\dots,n\}$ indicating that node $v$ is placed in layer $l(v)$, for all $v \in V$.

*Boolean decision variables.* $r(u,v) = 1$ if and only if edge $e = (u,v) \in E$ and $e$ is reversed, $l(u) > l(v)$, for all $u,v \in V$. Otherwise, $r(u,v) = 0$. $$\begin{aligned}
  \small
  %
 \text{Minimize} \qquad \wlen \sum_{(u,v) \in E} |l(u) - l(v)|
  %
                +\ \wrev \sum_{(u,v) \in E} r(u,v) \text{.}\end{aligned}$$

The sums represent the edge lengths, the number of dummy nodes, and the number of reversed edges, respectively. Constraints are defined as follows: $$\begin{aligned}
  \small
  %
   1 \ \leq\ l(v) \ \leq\  n \quad && \forall v\in V  \label{eqn:first} \\
   |l(u) - l(v)| \ \geq\  1 \quad && \forall (u,v) \in E\quad \label{eqn:second} \\
   n \cdot r(u,v) + l(v) \ \geq\  l(u) + 1 \quad && \forall (u,v) \in E \label{eqn:third}\end{aligned}$$ Constraint (\[eqn:first\]) restricts the range of possible layers. (\[eqn:second\]) ensures that the resulting layering is feasible. (\[eqn:third\]) binds the decision variables in $r$ to the layering, because $r$ is part of the objective, and $\wrev > 0$, $r(u,v)$ gets assigned 0 unless $l(v) < l(u)$, for all $(u,v) \in E$.

#### Variations.

The model can easily be extended to restrict the number of layers by replacing the $n$ in constraint (1) by a desired bound $b \leq n$.

The edge matrix can be extended to contain a weight $w_{u,v}$ for each edge $(u,v) \in E$. This can be helpful if further semantic information is available, about feedback edges that lend themselves well to be reversed.

The Heuristic Approach {#sec:heuristic}
======================

Interactive modeling tools providing automatic layout facilities require execution times significantly shorter than one second. As the IP formulation discussed in the previous section rarely meets this requirement, we present a heuristic to solve . It proceeds as follows. 1) Leaf nodes are removed iteratively, since it is trivial to place them with minimum edge length and desired edge direction. Note that therefore the heuristic is not yet able to improve on trees that yield a poor compactness. We leave this for future research. 2) For the (possibly cyclic) input graph an initial feasible layering is constructed which is used to deduce edge directions yielding an acyclic graph. 3) Using the network simplex method presented by Gansner [@GansnerKNV93], a solution with minimal edge length is created. 4) We execute a greedy improvement procedure after which we again deduce edge directions and re-attach the leaves. 5) We apply the network simplex algorithm a second time to get a valid layering with minimal edge lengths for the next steps of the layer-based approach. In the following we will discuss steps 2 and 4 in further detail.

#### Step 2: Layering Construction.

To construct an initial feasible solution we follow an idea that was first presented by McAllister as part of a greedy heuristic for the  [@McAllister99] and later extended by Pantrigo  [@PantrigoMDP12].

Nodes are assigned to distinct indexes, where as a start, a node is selected randomly, assigned to the first index, and added to a set of assigned nodes. Based on the set of assigned nodes a candidate list is formed, and the most promising node is assigned to the next index. As decision criterion we use the difference between the number of edges incident to unassigned nodes and the number of edges incident to assigned nodes. This procedure is repeated until all nodes are assigned to distinct indices (see ).

In contrast to McAllister, for we allow nodes to be added to either side of the set of assigned nodes, and decide the side based on the number of reversed edges that would emerge from placing a certain node on that side. For this we use a decreasing left index variable and an increasing right index variable.

remove random $v$ from $U$ $c \leftarrow v$

#### Step 4: Layering Improvement.

At this point a feasible layering with a minimum number of dummy nodes the chosen is given since we execute the network simplex method of Gansner beforehand. Thus we can only improve on the number of reversed edges. We determine possible *moves* and decide whether to take the move based on a *profit* value. Let a graph $G=(V,E)$ and a feasible layering $L$ be given. For ease of presentation, we define the following notions. An example: For a node $v$, $\tsuc$ are the nodes connected to $v$ via an outgoing edge of $v$ and are currently assigned to a layer with lower index than $v$’s index. Intuitively, $\tsuc$ (just as $\bpre$) are nodes connected by an edge pointing into the “wrong” direction. [$$\begin{aligned}
    &v.\tsuc = \{ w : (v,w) \in E \wedge L(v) > L(w) \}
    &&v.\bsuc = \{ w : (v,w) \in E \wedge L(v) < L(w) \} \\
    &v.\tpre = \{ w : (w,v) \in E \wedge L(w) < L(v) \}
    &&v.\bpre = \{ w : (w,v) \in E \wedge L(w) > L(v) \} \\
    &v.\tadj = v.\tsuc \cup v.\tpre
    &&v.\badj = v.\bsuc \cup v.\bpre\end{aligned}$$ ]{}

For all these functions we define suffixes that allow to query for a certain set of nodes before or after a certain index. For instance, for all top successors of $v$ before index $i$ we write $v.\textit{\scriptsize topSucBefore(i)} = \{ w : w \in v.\tsuc \wedge L(w) < i \}$. Let $move : V \mapsto \mathbb{N}$ denote a function assigning to each node a natural value. The function describes whether it is possible to move a node without violating the layering’s feasibility as well as how far the node should be moved. For instance, let for a node $v$ $\tpre$ be empty but $\tsuc$ be not empty. Thus, we can move $v$ to an arbitrary layer with lower index than $L(v)$. A good choice would be one layer before any of $v$’s $\tsuc$ since this would alter the connected edges to point downwards. [$$\begin{aligned}
    move(v) = \left\{ \begin{array}{l l}
            0 & \quad \text{if } v.\tsuc = \emptyset, \\
            L(v) - \min(\{L(w) : w \in v.\tsuc \}) + 1 & \quad \text{if } v.\tpre = \emptyset, \\
            L(v) - \max(\{L(w) : w \in v.\tpre \}) -  1 & \quad \text{otherwise.}
          \end{array} \right.\end{aligned}$$ ]{}

Let $\mbox{\itshape profit} : V \times \mathbb{N} \times \mathbb{N} \mapsto \mathbb{Z}$ denote a function assigning a quality score to each node $v$ if it were moved by $m \in \mathbb{N}$ to a different layer $x$, if it is worth to increase some edges’ lengths for a subset of them to point downwards. Note that we reuse and here but do not expect them to have an impact as strong as for the IP. For the rest of the paper we fix them to 1 and 5. [$$\begin{aligned}
    \mbox{\itshape profit}(v, m, x) = \left\{ \begin{array}{l l}
            0 & \quad \text{if } m \leq 1, \\
            \wlen (m | v.\textit{\scriptsize topAdjBefore(x)} | - m | v.\badj | ) & \quad \\
            + \enspace \wrev | v.\textit{\scriptsize topSucAfter(x)} | & \quad \text{otherwise.}
          \end{array} \right.\end{aligned}$$ ]{}

As seen in , the $move$ and $\mbox{\itshape profit}$ functions are determined initially for a given feasible layering. A queue, sorted based on profit values, is then used to successively perform moves that yield a profit. After a move of node $n$, both functions can be updated for all nodes in the adjacency of $n$.

#### Time Complexity.

Removing leaf nodes requires linear time, $O(|V|+|E|)$. is quadratic in the number of nodes, $O(|V|^2)$. The while loop has to assign an index to every node and the two inner for loops are, for a complete graph, iterated $\frac{|V|}{2}$ times on average. Determining the next candidate (lines 15–16) could be accelerated using dedicated data structures. The improvement step strongly depends on the input graph. The network simplex method runs reportedly fast in practice [@GansnerKNV93], although it has not been proven to be polynomial. Our evaluations showed that the heuristic’s overall execution time is clearly dominated by the network simplex method ().

Evaluation {#sec:evaluations}
==========

In this section we evaluate three points: 1) the general feasibility of to improve the compactness of drawings, 2) the quality of metric estimations for area and aspect ratio, and 3) the performance of the presented IP and heuristic. Our main metrics of interest here are height, area, and aspect ratio, as defined in an earlier paper [@GutwengervHM+14]. Remember that the layer-based approach is defined as a pipeline of several independent steps. After the layering phase, which is the focus of our research here, these latter two metrics can only be estimated using the number of dummy nodes, the number of layers, and the maximal number of nodes in a layer. Results can be seen in and , which we will discuss in more detail in the remainder of this section.

#### Obtaining a Final Drawing.

To collect all metrics we desire, we have to create a final drawing of a graph. Over time numerous strategies have been presented for each step of the layer-based approach, we thus present several alternatives. To break cycles we use a popular heuristic by Eades  [@EadesLS93]. To determine a layering we use our newly presented approach (both the IP method and heuristic, denoted by and ) and alternatively the network simplex method presented by Gansner  [@GansnerKNV93]. We denote the combination of the cycle breaking of Eades and the layering of Gansner as and consider it to be an alternative to . Crossings between pairs of layers are minimized using a layer sweep method in conjunction with the barycenter heuristic, as originally proposed by [Sugiyama  [@SugiyamaTT81]]{}. We employ two different strategies to determine fixed coordinates for nodes within the layers. First, we consider a method introduced by Buchheim that was extended by Brandes and K[ö]{}pf [@BuchheimJL01; @BrandesK02], which we denote as . Second, we use a method inspired by Sander [@Sander96a] that we call . Edges are routed either using polylines () or orthogonal segments (). The orthogonal router is based on the methods presented by Sander [@Sander04]. Overall, this gives twelve setups of the algorithm: three layering methods, two node placement algorithms, and two edge routing procedures. In the following, let denote the used weights. If we do not further qualify , we refer to the IP model.

\

#### Test Graphs.

Our new approach is intended to improve the drawings of graphs with a large height and relatively small width, hence unfavorable aspect ratio. Nevertheless, we also evaluate the generality of the approach using a set of 160 randomly generated graphs with 17 to 60 nodes and an average of $1.5$ edges per node. The graphs were generated by creating a number of nodes, assigning out-degrees to each node such that the sum of outgoing edges is $1.5$ times the nodes, and finally creating the outgoing edges with a randomly chosen target node. Unconnected nodes were removed. Second, we filtered the graph set provided by North[^1] [@DiBattistaGLP+97] based on the aspect ratio and selected 146 graphs that have at least 20 nodes and a drawing[^2] with an aspect ratio below $0.5$, are at least twice as high as wide. We also removed plain paths, that is, pairs of nodes connected by exactly one edge, and trees. For these special cases in its current form would not change the resulting number of reversed edges as all edges can be drawn with length $1$. This is also true for any bipartite graph. Note however that can easily incorporate a bound on the number of layers which can straightforwardly be used to force more edges to be reversed, resulting in a drawing with better aspect ratio.

#### General Feasibility of GLP.

An exemplary result of the approach compared to can be seen in . For that specific drawing, produces fewer reversed edges, fewer dummy nodes, and less area (both in width and height). For all tested setups the average effective height and area (normalized by the number of nodes) of and the heuristic are smaller than ’s, see . The average aspect ratios come closer to $1.0$. For simplicity, in this paper we desire aspect ratios closer to $1.0$. For a more detailed discussion on this topic see Gutwenger  [@GutwengervHM+14].

Furthermore, we found that by altering the weights and a trade-off between reversed edges and resulting dummy nodes (and thus area and aspect ratio) can be achieved, which can be seen in Tab.\[tab:random\_results\].

The results for the North graphs are similar. Since the North graphs are acyclic, the cycle breaking phase is not required and current layering algorithms cannot improve the height. The approach, however, can freely reverse edges and hereby change the height and aspect ratio. Results can be seen in Tab. \[tab:highar\_results\]. Clearly, has no reversed edges as all graphs are acyclic. starts with an average of $2.7$ reversed edges and the value constantly decreases with an increased weight on reversed edges. The number of dummy nodes on the other hand constantly decreases from $141.3$ for to $39.9$ for .

The average height and average area of the final drawings decrease with an increasing number of reversed edges. For the average height and area are 38.2and 33.8smaller than . The aspect ratio changes from an average of 0.20 for to 0.34 for .

The results show that for the selected graphs, for which current methods cannot improve on height, the weights of the new approach allow to find a satisfying trade-off between reversed edges and dummy nodes. Furthermore, the improvements in compactness stem solely from the selection of weights, not from an upper bound on the number of layers. Naturally, such a bound can further improve the aspect ratio and height.

  ----------------------------------------------------------------- -------- -------- -------- -------- -------- -------- -------- -------- -------- -------- ------- -------
  [Edge routing]{}                                                                                                                                                    
  (lr)[2-7]{} (lr)[8-13]{} [Node coord.]{}                                                                                                                            
  (lr)[2-4]{} (lr)[5-7]{} (lr)[8-10]{} (lr)[11-13]{} [Layering]{}                                                                                                     
  Height                                                               1,165    1,043      898      943      824      732      790      711      652      817     746     678
  Area                                                                20,194   18,683   15,575   12,383   11,035   10,075   13,582   12,642   11,272   10,666   9,917   9,295
  Aspect ratio                                                          0.59     0.67     0.67     0.55     0.64     0.64     0.84     0.96     0.90     0.63    0.70    0.68
  ----------------------------------------------------------------- -------- -------- -------- -------- -------- -------- -------- -------- -------- -------- ------- -------

  :  Results for final drawings of the set of random graphs, when applying different layout strategies. For $\wlen = 1$ and $\wrev = 30$ were used. Area is normalized by a graph’s node count. The most interesting comparisons are between columns where and use the same strategies for the remaining steps. Detailed results can be found in the appendix (\[sec:detailed\_results\]). []{data-label="tab:metric_results"}

#### Metric Estimations.

presents results that were measured on the final drawing of a graph. As mentioned earlier, after the layering step these values are not available and estimations are commonly used to deduce the quality of a result. For our example graphs, the estimated area reduced from $222.9$ () to $187.4$ () on average. The estimated aspect ratios increase on average from $0.74$ to $0.84$. Both tendencies conform to the averaged effective values in , and the perform better. However, we observed that for 64of the graphs the tendency of the estimated area contradicts the tendency of the effective area.[^3] 54when not considering dummy nodes. In other words, for a specific graph the estimated area might be decreased for compared to but the effective area is increased for (or vice versa). This clearly indicates that an estimation can be misleading. Besides, node placement and edge routing can have a non-negligible impact on the aspect ratio and compactness of the final drawing.

#### Performance of the Heuristic.

Results for final drawings using the presented heuristic are included in and are comparable to , the heuristic performs better than the desired metrics.

Tab. \[tab:random\_results\] and Tab. \[tab:highar\_results\] underline this result and show that the improvement step of the heuristic clearly improves on all measured metrics. Further, more detailed results, can be found in the appendix. Nevertheless, the heuristic yields significantly more reversed edges. When aiming for compactness, we consider this to be acceptable.

#### Execution Times. {#sec:execution_times}

To solve the IP model we used CPLEX 12.6 and executed the evaluations on a server with an Intel Xeon E5540 CPU and 24 GB memory. The execution times for vary between 476ms for a graph with 19 nodes and 541s for a graph with 58 nodes and exponentially increase with the graph’s node count. This is impracticable for interactive tools that rely on automatic layout, but is fast enough to collect optimal results for medium sized graphs.

The execution time of the heuristic is compared to and was measured on a laptop with an Intel i7-3537U CPU and 8 GB memory. The reported time includes only the first two steps of the layer-based approach. It turns out that the execution time of the heuristic is on average 2.3 times longer than . This seems reasonable, as it involves two executions of the network simplex layering method. For the tested graphs, the construction and improvement steps of the heuristic hardly contribute to its overall execution time. The effective execution time ranges between 0.1ms and 10.0ms for and 0.3ms and 19.7ms for the heuristic. Hence, the heuristic is fast enough to be used in interactive tools. We also ran the algorithm five times for five randomly generated graphs with 1000 nodes and 1500 edges. required an average of 374ms, the heuristic 666ms with about 4ms for construction an 2ms for improvement. This shows that the time contribution of the latter two is negligible even for larger graphs.

Conclusion {#sec:conclusion}
==========

In this paper we address problems with current methods for the first two phases of the layer-based layout approach. We argue that separately performing cycle breaking and layering is disadvantageous when aiming for compactness. We present a configurable method for the layering phase that, compared to other state-of-the-art methods, shows on average improved performance on compactness. That is, the number of dummy nodes is reduced significantly for most graphs and can never increase. While the number of dummy nodes only allows for an estimation of the area, the effective area of the final drawing is reduced as well. Furthermore, graph instances for which current methods yield unfavorable aspect ratios can easily be improved. Also, the presented heuristic clearly improves on the desired metrics. Depending on the application, a slight increase in the number of reversed edges is often acceptable.

We want to stress that the common practice to determine the quality of methods developed for certain phases of the layer-based approach based on metrics that represent estimations of the properties of the final drawing is error-prone. For instance, estimations of the area and aspect ratio after the layering phase can vary significantly from the effective values of the final drawing and strongly depend on the used strategies for computing node and edge coordinates.

Future work will include improving the heuristic, selecting the initial node based on a certain criterion instead of randomly in should improve the results. We also plan to incorporate hard bounds on the width of a drawing. It is important that methods support to prevent, or at least to strongly penalize, the reversal of certain edges, since certain diagram types demand several edges to be drawn forwards. Also, user studies could help understand which edges are natural candidates to be reversed from a human’s perspective.

Furthermore, in an accompanying technical report we present a variation of where we fix the size of the while remaining free in the choice of which edges to reverse [@RueeggESvH15], which so far has only been evaluated using integer programming.

### **Acknowledgements.**

We thank Chris Mears for support regarding the initial IP formulation. We further thank Tim Dwyer and Petra Mutzel for valuable discussions. This work was supported by the German Research Foundation under the project *Compact Graph Drawing with Port Constraints*\
(ComDraPor, DFG HA 4407/8-1).

Appendix
========

Example Drawings of North Graphs
--------------------------------

Detailed Results {#sec:detailed_results}
----------------

[^1]: <http://www.graphdrawing.org/data/>

[^2]: Created using and .

[^3]: Using and .
