Top

previous chapter Node Overlap Removal by Growing a Tree

next chapter Peacock Bundles: Bundle Coloring for Graphs wit...

Hint

Swipe to navigate through the chapters of this book

2016 | OriginalPaper | Chapter

Placing Arrows in Directed Graph Drawings

Read first chapter

Authors: Carla Binucci, Markus Chimani, Walter Didimo, Giuseppe Liotta, Fabrizio Montecchiani

Publisher: Springer International Publishing

Published in: Graph Drawing and Network Visualization

» Get access to the full-text

Abstract

We consider the problem of placing arrow heads in directed graph drawings without them overlapping other drawn objects. This gives drawings where edge directions can be deduced unambiguously. We show hardness of the problem, present exact and heuristic algorithms, and report on a practical study.

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

Binucci, C., Chimani, M., Didimo, W., Liotta, G., Montecchiani, F.: Placing arrows in directed graph drawings. ArXiv e-prints abs/1608.08505 (2016). http://arxiv.org/abs/1608.08505v1

Brandes, U., Finocchi, I., Nöllenburg, M., Quigley, A.: Empirical evaluation for graph drawing (Dagstuhl seminar 15052). Dagstuhl Rep. 5(1), 243–258 (2015)

Chimani, M., Gutwenger, C., Jünger, M., Klau, G.W., Klein, K., Mutzel, P.: The open graph drawing framework (OGDF). In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, chap. 17. CRC Press, Boca Raton (2014). www.ogdf.net

Gemsa, A., Niedermann, B., Nöllenburg, M.: Trajectory-based dynamic map labeling. In: Cai, L., Cheng, S.-W., Lam, T.-W. (eds.) ISAAC 2013. LNCS, vol. 8283, pp. 413–423. Springer, Heidelberg (2013). doi: 10.1007/978-3-642-45030-3_39 CrossRef

Gemsa, A., Nöllenburg, M., Rutter, I.: Evaluation of labeling strategies for rotating maps. In: Gudmundsson, J., Katajainen, J. (eds.) SEA 2014. LNCS, vol. 8504, pp. 235–246. Springer, Heidelberg (2014). doi: 10.1007/978-3-319-07959-2_20

Hachul, S., Jünger, M.: Drawing large graphs with a potential-field-based multilevel algorithm. In: Pach, J. (ed.) GD 2004. LNCS, vol. 3383, pp. 285–295. Springer, Heidelberg (2005). doi: 10.1007/978-3-540-31843-9_29 CrossRef

Holten, D., Isenberg, P., van Wijk, J.J., Fekete, J.: An extended evaluation of the readability of tapered, animated, and textured directed-edge representations in node-link graphs. In: IEEE PacificVis 2011, pp. 195–202. IEEE (2011)

Holten, D., van Wijk, J.J.: A user study on visualizing directed edges in graphs. In: CHI 2009, pp. 2299–2308. ACM (2009)

Kakoulis, K.G., Tollis, I.G.: On the complexity of the edge label placement problem. Comput. Geom. 18(1), 1–17 (2001) MathSciNetCrossRefMATH

10.

Kakoulis, K.G., Tollis, I.G.: Labeling algorithms. In: Tamassia, R. (ed.) Handbook on Graph Drawing and Visualization, pp. 489–515. Chapman and Hall/CRC, New York (2013)

11.

van Kreveld, M.J., Strijk, T., Wolff, A.: Point labeling with sliding labels. Comput. Geom. 13(1), 21–47 (1999) MathSciNetCrossRefMATH

12.

Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982) MathSciNetCrossRefMATH

13.

Marks, J., Shieber, S.: The computational complexity of cartographic label placement. Technical Report 05-91, Harvard University (1991)

14.

North graphs. http://www.graphdrawing.org/data.html

15.

Strijk, T., van Kreveld, M.J.: Practical extensions of point labeling in the slider model. GeoInformatica 6(2), 181–197 (2002) CrossRefMATH

16.

Strijk, T., Wolff, A.: Labeling points with circles. Int. J. Comput. Geom. Appl. 11(2), 181–195 (2001) MathSciNetCrossRefMATH

17.

Wagner, F., Wolff, A., Kapoor, V., Strijk, T.: Three rules suffice for good label placement. Algorithmica 30(2), 334–349 (2001) MathSciNetCrossRefMATH

18.

Wolff, A.: A simple proof for the NP-hardness of edge labeling. Technical Report 11/2000, Institute of Mathematics and Computer Science, Ernst Moritz Arndt University Greifswald (2000)

Title

Placing Arrows in Directed Graph Drawings

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_4

Authors:

Carla Binucci
Markus Chimani
Walter Didimo
Giuseppe Liotta
Fabrizio Montecchiani

Publisher

Springer International Publishing

Sequence number

Premium Partner

Image Credits