Top

previous chapter Algorithms for Visualizing Phylogenetic Networks

next chapter Compact Layered Drawings of General Directed Gr...

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

A Generalization of the Directed Graph Layering Problem

Read first chapter

Authors: Ulf Rüegg, Thorsten Ehlers, Miro Spönemann, Reinhard von Hanxleden

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

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.

Please log in to get access to this content

To get access to this content you need the following product:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 69.000 Bücher
über 500 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 50.000 Bücher
über 380 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Umwelt
Maschinenbau + Werkstoffe

Testen Sie jetzt 30 Tage kostenlos.

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 58.000 Bücher
über 300 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Testen Sie jetzt 30 Tage kostenlos.

inform now

http://www.graphdrawing.org/data/.

Created using BK and Poly.

Using BK and Poly.

Brandes, U., Köpf, B.: Fast and simple horizontal coordinate assignment. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 31–44. Springer, Heidelberg (2002). doi: 10.1007/3-540-45848-4_3 CrossRef

Buchheim, C., Jünger, M., Leipert, S.: A fast layout algorithm for k-level graphs. In: Marks, J. (ed.) GD 2000. LNCS, vol. 1984, pp. 229–240. Springer, Heidelberg (2001). doi: 10.1007/3-540-44541-2_22 CrossRef

Battista, G., Garg, A., Liotta, G., Parise, A., Tamassia, R., Tassinari, E., Vargiu, F., Vismara, L.: Drawing directed acyclic graphs: an experimental study. In: North, S. (ed.) GD 1996. LNCS, vol. 1190, pp. 76–91. Springer, Heidelberg (1997). doi: 10.1007/3-540-62495-3_39 CrossRef

Dwyer, T., Koren, Y.: DIG-COLA: directed graph layout through constrained energy minimization. In: Proceedings of the IEEE Symposium on Information Visualization (INFOVIS 2005), pp. 65–72, October 2005

Eades, P., Lin, X., Smyth, W.F.: A fast and effective heuristic for the feedback arc set problem. Inf. Process. Lett. 47(6), 319–323 (1993) MathSciNetCrossRefMATH

Eades, P., Sugiyama, K.: How to draw a directed graph. J. Inf. Process. 13(4), 424–437 (1990) MATH

Gansner, E.R., Koutsofios, E., North, S.C., Vo, K.P.: A technique for drawing directed graphs. Softw. Eng. 19(3), 214–230 (1993) CrossRef

Gutwenger, C., von Hanxleden, R., Mutzel, P., Rüegg, U., Spönemann, M.: Examining the compactness of automatic layout algorithms for practical diagrams. In: Proceedings of the Workshop on Graph Visualization in Practice (GraphViP 2014), Melbourne, Australia, July 2014

Healy, P., Nikolov, N.S.: A branch-and-cut approach to the directed acyclic graph layering problem. In: Goodrich, M.T., Kobourov, S.G. (eds.) GD 2002. LNCS, vol. 2528, pp. 98–109. Springer, Heidelberg (2002). doi: 10.1007/3-540-36151-0_10 CrossRef

10.

Healy, P., Nikolov, N.S.: How to layer a directed acyclic graph. In: Mutzel, P., Jünger, M., Leipert, S. (eds.) GD 2001. LNCS, vol. 2265, pp. 16–30. Springer, Heidelberg (2002). doi: 10.1007/3-540-45848-4_2 CrossRef

11.

Healy, P., Nikolov, N.S.: Hierarchical drawing algorithms. In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, pp. 409–453. CRC Press, Boca Raton (2013)

12.

McAllister, A.J.: A new heuristic algorithm for the linear arrangement problem. University of New Brunswick, Technical report (1999)

13.

Nachmanson, L., Robertson, G., Lee, B.: Drawing graphs with GLEE. In: Hong, S.-H., Nishizeki, T., Quan, W. (eds.) GD 2007. LNCS, vol. 4875, pp. 389–394. Springer, Heidelberg (2008). doi: 10.1007/978-3-540-77537-9_38 CrossRef

14.

Nikolov, N.S., Tarassov, A., Branke, J.: In search for efficient heuristics for minimum-width graph layering with consideration of dummy nodes. J. Exp. Algorithmics 10 (2005)

15.

Pantrigo, J., Martí, R., Duarte, A., Pardo, E.: Scatter search for the cutwidth minimization problem. Ann. Oper. Res. 199(1), 285–304 (2012) MathSciNetCrossRefMATH

16.

Rüegg, U., Ehlers, T., Spönemann, M., von Hanxleden, R.: A generalization of the directed graph layering problem. Technical report 1501, Kiel University, Department of Computer Science, ISSN 2192–6247, February 2015

17.

Rüegg, U., Ehlers, T., Spönemann, M., von Hanxleden, R.: A generalization of the directed graph layering problem, August 2016. arXiv:1608.07809 [cs.OH]

18.

Sander, G.: A fast heuristic for hierarchical Manhattan layout. In: Brandenburg, F.J. (ed.) GD 1995. LNCS, vol. 1027, pp. 447–458. Springer, Heidelberg (1996). doi: 10.1007/BFb0021828 CrossRef

19.

Sander, G.: Layout of directed hypergraphs with orthogonal hyperedges. In: Liotta, G. (ed.) GD 2003. LNCS, vol. 2912, pp. 381–386. Springer, Heidelberg (2004). doi: 10.1007/978-3-540-24595-7_35 CrossRef

20.

Sugiyama, K., Tagawa, S., Toda, M.: Methods for visual understanding of hierarchical system structures. IEEE Trans. Syst. Man Cybern. 11(2), 109–125 (1981) MathSciNetCrossRef

Title

A Generalization of the Directed Graph Layering Problem

Book

Graph Drawing and Network Visualization

Print ISBN: 978-3-319-50105-5

Electronic ISBN: 978-3-319-50106-2

https://doi.org/10.1007/978-3-319-50106-2

DOI

https://doi.org/10.1007/978-3-319-50106-2_16

Authors:

Ulf Rüegg
Thorsten Ehlers
Miro Spönemann
Reinhard von Hanxleden

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits