![]() |
Home | Issues | About JGAA | Instructions for Authors |
Special issue on Selected papers from the Twenty-fourth International Symposium on Graph Drawing and Network Visualization, GD 2016
DOI: 10.7155/jgaa.00441
Generalized Layerings for Arbitrary and Fixed Drawing Areas
Vol. 21, no. 5, pp. 823-856, 2017. Regular paper.
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.
The drawings resulting from GLP also turn out
to be more suitable
for making the best possible use of a given drawing area.
However, we show that a specialized variant of GLP
can yield considerable improvements
w.r.t. this particular optimization goal.
|
Submitted: December 2016.
Reviewed: March 2017.
Revised: April 2017.
Accepted: July 2017.
Final: July 2017.
Published: October 2017.
|
Journal Supporters
|