Compact layered drawings of general directed graphs

DOI10.1007/978-3-319-50106-2_17MaRDI QIDQ2961517zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Adalat Jabrayilov, Sven Mallach, Petra Mutzel, Ulf Rüegg, Reinhard von Hanxleden

Publication date 21 February 2017

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1609.01755

zbMATH Keywords

layer assignmentlayer-based layoutmixed integer programming

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph theory (including graph drawing) in computer science (68R10) Mixed integer programming (90C11) Approximation methods and heuristics in mathematical programming (90C59)

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

Recommendations

• Generalized layerings for arbitrary and fixed drawing areas
• A generalization of the directed graph layering problem
• scientific article; zbMATH DE number 2084263
• scientific article; zbMATH DE number 1974111
• scientific article; zbMATH DE number 1953098

Cites work

• A fast and effective heuristic for the feedback arc set problem
• A generalization of the directed graph layering problem
• Compact layered drawings of general directed graphs
• Drawing Graphs with GLEE
• scientific article; zbMATH DE number 2084263 (Why is no real title available?)
• scientific article; zbMATH DE number 30296 (Why is no real title available?)
• scientific article; zbMATH DE number 1974111 (Why is no real title available?)
• In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes
• Optimal scheduling for two-processor systems
• The Eigenvalues of a Graph and Its Chromatic Number

Cited in

(13)

• Improved mixed-integer programming models for the multiprocessor scheduling problem with communication delays
• A flow formulation for horizontal coordinate assignment with prescribed width
• A natural quadratic approach to the generalized graph layering problem
• L-Drawings of Directed Graphs
• A generalization of the directed graph layering problem
• Compact layered drawings of general directed graphs
• scientific article; zbMATH DE number 2084263 (Why is no real title available?)
• In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes
• scientific article; zbMATH DE number 1974111 (Why is no real title available?)
• A flow formulation for horizontal coordinate assignment with prescribed width
• An Efficient Implementation of Sugiyama's Algorithm for Layered Graph Drawing
• Generalized layerings for arbitrary and fixed drawing areas
• 2-Layer Graph Drawings with Bounded Pathwidth

This page was built for publication: Compact layered drawings of general directed graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2961517)