A Generalization of the Directed Graph Layering Problem
The Directed Layering Problem (DLP) solves a step of the widely used layer-based layout approach to automatically draw directed acyclic graphs. To cater for cyclic graphs, classically 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 show GLP to be NP- complete, present integer programming models to solve it, 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.
Use and reproduction:No Creative Commons license - The provisions of the German Copyright Act (UrhG) apply.Please note that individual components of the publication may be subject to other licensing or copyright conditions.