A generalization of the directed graph layering problem

DOI10.1007/978-3-319-50106-2_16MaRDI QIDQ2961516zbMATH OpenOpenAlexFDO

Authors Ulf Rüegg, Thorsten Ehlers, Miro Spönemann, 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/1608.07809

zbMATH Keywords

feedback arc setinteger programminglayer assignmentlayer-based layoutlinear arrangement

Mathematics Subject Classification ID

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

Abstract: 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.

Recommendations

• Generalized layerings for arbitrary and fixed drawing areas
• Compact layered drawings of general directed graphs
• 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
• Drawing directed acyclic graphs: an experimental study
• Drawing Graphs with GLEE
• scientific article; zbMATH DE number 2084263 (Why is no real title available?)
• scientific article; zbMATH DE number 2084264 (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?)
• scientific article; zbMATH DE number 2080102 (Why is no real title available?)
• In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes
• Scatter search for the cutwidth minimization problem

Cited in

(13)

• Width-restricted layering of acyclic digraphs with consideration of dummy nodes
• Layered graph approaches for combinatorial optimization problems
• A natural quadratic approach to the generalized graph layering problem
• 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 1953098 (Why is no real title available?)
• scientific article; zbMATH DE number 1974111 (Why is no real title available?)
• Traversing Layered Graphs Using the Work Function Algorithm
• Generalized layerings for arbitrary and fixed drawing areas
• The eclipse layout kernel (software abstract)
• Generalized \(k\)-ary tanglegrams on level graphs: a satisfiability-based approach and its evaluation

This page was built for publication: A generalization of the directed graph layering problem

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