Compact Layered Drawings of General Directed Graphs

Jabrayilov, Adalat and Mallach, Sven and Mutzel, Petra and Rüegg, Ulf and von Hanxleden, Reinhard (2016) Compact Layered Drawings of General Directed Graphs.
Published In: Graph Drawing and Network Visualization: 24th International Symposium, GD 2016, Athens, Greece, September 19-21, 2016, Revised Selected Papers, Lecture Notes in Computer Science. 9801 Springer 2016, pp. 209-221.


We consider the problem of layering general directed graphs under height and possibly also width constraints. Given a directed graphG = (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 NP-hard. 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.

Full text not available from this repository.
Editorial actions: View Item View Item (Login required)
Deposit Information:
Depositing User: Sven Mallach
Date Deposited: 16 Sep 2016 13:29
Last Modified: 24 Oct 2017 11:42