A flow formulation for horizontal coordinate assignment with prescribed width. (English) Zbl 1419.05147

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


05C62 Graph representations (geometric and intersection representations, etc.)
05C20 Directed graphs (digraphs), tournaments


Full Text: DOI


[1] R. K. Ahuja, T. L. Magnanti, and J. B. Orlin. Network flows - theory, algorithms and applications. Prentice Hall, 1993. · Zbl 1201.90001
[2] C. Bachmaier, A. Gleißner, and A. Hofmeier.Dagmar:Library for dags.Technical Report MIP-1202, University of Passau, Germany, 2012.URL:
[3] J. Bang-Jensen and G. Gutin. Digraphs: Theory, Algorithms and Applications. Monographs in Mathematics. Springer, 2008. · Zbl 1001.05002
[4] U. Brandes and B. K¨opf. Fast and simple horizontal coordinate assignment. In P. Mutzel, M. J¨unger, and S. Leipert, editors, Graph Drawing, 9th International Symposium, GD 2001, volume 2265 of LNCS, pages 31- 44. Springer, 2001. · Zbl 1054.68569
[5] J. Branke, S. Leppert, M. Middendorf, and P. Eades. Width-restricted layering of acyclic digraphs with consideration of dummy nodes. Information Processing Letters, 81(2):59-63, 2002. · Zbl 1032.68117
[6] C. Buchheim, M. J¨unger, and S. Leipert. A fast layout algorithm for k -level graphs. In J. Marks, editor, Graph Drawing, 8th International Symposium, GD 2000, volume 1984 of LNCS, pages 229-240. Springer, 2000. · Zbl 1043.68609
[7] M. Chimani, C. Gutwenger, M. J¨unger, G. W. Klau, K. Klein, and P. Mutzel. The open graph drawing framework (OGDF). In R. Tamassia, editor, Handbook on Graph Drawing and Visualization., pages 543-569. Chapman and Hall/CRC, 2013.
[8] E. G. Coffman and R. L. Graham. Optimal scheduling for two-processor systems. Acta Informatica, 1(3):200-213, 1972. · Zbl 0248.68023
[9] W. W.-M. Dai and E. S. Kuh. Global spacing of building-block layout. In Proceedings of the IFIP International Conference on Very Large Scale Integration, VLSI’87, pages 193-205, 1987.
[10] P. Eades, X. Lin, and R. Tamassia. An algorithm for drawing a hierarchical graph. Int. J. Comput. Geometry Appl., 6(2):145-156, 1996. · Zbl 0854.68035
[11] M. Forster. Applying crossing reduction strategies to layered compound graphs.In Graph Drawing, 10th International Symposium, GD 2002, volume 2528 of LNCS, pages 276-284. Springer, 2002. · Zbl 1037.68585
[12] E. R. Gansner, E. Koutsofios, S. C. North, and K.-P. Vo. A technique for drawing directed graphs. Software Engineering, 19(3):214-230, 1993.
[13] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman, 1979. · Zbl 0411.68039
[14] P. Healy and N. S. Nikolov.A branch-and-cut approach to the directed acyclic graph layering problem.In S. G. Kobourov and M. T. Goodrich, editors, Graph Drawing, 10th International Symposium, GD 2002, volume 2528 of LNCS, pages 98-109. Springer, 2002. · Zbl 1037.68590
[15] P. Healy and N. S. Nikolov. Hierarchical drawing algorithms. In R. Tamassia, editor, Handbook on Graph Drawing and Visualization., pages 409-453. Chapman and Hall/CRC, 2013.
[16] A. Jabrayilov, S. Mallach, P. Mutzel, U. R¨uegg, and R. von Hanxleden. Compact layered drawings of general directed graphs.In Y. Hu and M. N¨ollenburg, editors, Graph Drawing and Network Visualization - 24th International Symposium, GD 2016, volume 9801 of LNCS, pages 209-221. Springer, 2016. · Zbl 1478.68245
[17] G. W. Klau, K. Klein, and P. Mutzel. An Experimental Comparison of Orthogonal Compaction Algorithms (Extended Abstract). In J. Marks, editor, Graph Drawing, 8th International Symposium, GD 2000, volume 1984 of LNCS, pages 37-51. Springer, 2000. · Zbl 1043.68626
[18] L. Nachmanson, G. G. Robertson, and B. Lee. Drawing graphs with GLEE. In S. Hong, T. Nishizeki, and W. Quan, editors, Graph Drawing, 15th International Symposium, GD 2007, volume 4875 of LNCS, pages 389-394. Springer, 2007. · Zbl 1137.68500
[19] U. R¨uegg, C. D. Schulze, J. J. Carstens, and R. von Hanxleden. Sizeand port-aware horizontal node coordinate assignment. In E. Di Giacomo and A. Lubiw, editors, Graph Drawing and Network Visualization - 23rd International Symposium, GD 2015, volume 9411 of LNCS, pages 139-150, 2015. · Zbl 1471.68208
[20] G. Sander. A fast heuristic for hierarchical manhattan layout. In F. Brandenburg, editor, Graph Drawing, Symposium on Graph Drawing, GD ’95, volume 1027 of LNCS, pages 447-458. Springer, 1995.
[21] K. Sugiyama, S. Tagawa, and M. Toda. Methods for visual understanding of hierarchical system structures. · Zbl 0492.90001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.