  The Directed Layering Problem (DLP) 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
Feedback Arc Set Problem (FASP) to make the graph acyclic before a layering is
determined. Here we present the Generalized Layering Problem (GLP), which
solves the combination of DLP and FASP simultaneously, allowing general graphs
as input. We present an integer programming model and a heuristic to solve the
NP-complete GLP and perform thorough evaluations on different sets of graphs
and with different implementations for the steps of the layer-based approach.
We observe that GLP reduces the number of dummy nodes significantly, can
produce more compact drawings, and improves on graphs where DLP yields poor
aspect ratios.
