A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width

Authors

  • Michael Jünger
  • Petra Mutzel
  • Christiane Spisla

DOI:

https://doi.org/10.7155/jgaa.00500

Keywords:

graph drawing , sugiyama framework , coordinate assignment , width , edge length , minimum cost flow

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.

Downloads

Download data is not yet available.

Downloads

Published

2019-09-01

How to Cite

Jünger, M., Mutzel, P., & Spisla, C. (2019). A Flow Formulation for Horizontal Coordinate Assignment with Prescribed Width. Journal of Graph Algorithms and Applications, 23(3), 499–524. https://doi.org/10.7155/jgaa.00500