A Generalization of the Directed Graph Layering ProblemRüegg, Ulf and Ehlers, Thorsten and Spönemann, Miro and von Hanxleden, Reinhard (2016) A Generalization of the Directed Graph Layering Problem. In: Graph Drawing and Network Visualization. GD 2016, September, 19.  21., 2016 , pp. 196208(Official URL: http://dx.doi.org/10.1007/9783319501062_16). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319501062_16
AbstractThe Directed Layering Problem (DLP) solves a step of the widely used layerbased 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 NPcomplete GLP and perform thorough evaluations on different sets of graphs and with different implementations for the steps of the layerbased 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.
Actions (login required)
