Journal of Graph Algorithms and Applications
|Home||Issues||About JGAA||Instructions for Authors|
Special issue on Selected papers from the Twenty-sixth International Symposium on Graph Drawing and Network Visualization, GD 2018
A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width
Vol. 23, no. 3, pp. 499-524, 2019. Regular paper.
Abstract We consider the coordinate assignment phase of the Sugiyama framework for drawing directed graphs in a hierarchical style. The extensive literature in this area has given comparatively little attention to a prescribed width of the drawing. We present a minimum cost flow formulation that supports prescribed width and optionally other criteria like lower and upper bounds on the distance of neighboring nodes in a layer or enforced vertical edge segments. In our experiments we demonstrate that our approach can compete with state-of-the-art algorithms.
Submitted: November 2018.
Reviewed: January 2019.
Revised: June 2019.
Accepted: June 2019.
Final: July 2019.
Published: September 2019.
Communicated by Therese Biedl and Andreas Kerren