×

zbMATH — the first resource for mathematics

Placing arrows in directed graph drawings. (English) Zbl 06687285
Hu, Yifan (ed.) et al., Graph drawing and network visualization. 24th international symposium, GD 2016, Athens, Greece, September 19–21, 2016. Revised selected papers. Cham: Springer (ISBN 978-3-319-50105-5/pbk; 978-3-319-50106-2/ebook). Lecture Notes in Computer Science 9801, 44-51 (2016).
Summary: 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.
For the entire collection see [Zbl 1352.68012].

MSC:
68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
Software:
OGDF
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] 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 · Zbl 06687285
[2] Brandes, U., Finocchi, I., Nöllenburg, M., Quigley, A.: Empirical evaluation for graph drawing (Dagstuhl seminar 15052). Dagstuhl Rep. 5(1), 243–258 (2015)
[3] 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
[4] 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 · Zbl 1406.68116 · doi:10.1007/978-3-642-45030-3_39
[5] 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 · Zbl 06349901 · doi:10.1007/978-3-319-07959-2_20
[6] 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 · Zbl 1111.68583 · doi:10.1007/978-3-540-31843-9_29
[7] 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) · doi:10.1109/PACIFICVIS.2011.5742390
[8] Holten, D., van Wijk, J.J.: A user study on visualizing directed edges in graphs. In: CHI 2009, pp. 2299–2308. ACM (2009) · doi:10.1145/1518701.1519054
[9] Kakoulis, K.G., Tollis, I.G.: On the complexity of the edge label placement problem. Comput. Geom. 18(1), 1–17 (2001) · Zbl 0976.68173 · doi:10.1016/S0925-7721(00)00025-0
[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) · Zbl 0930.68153 · doi:10.1016/S0925-7721(99)00005-X
[12] Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329–343 (1982) · Zbl 0478.68043 · doi:10.1137/0211025
[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) · Zbl 1035.68683 · doi:10.1023/A:1015202410664
[16] Strijk, T., Wolff, A.: Labeling points with circles. Int. J. Comput. Geom. Appl. 11(2), 181–195 (2001) · Zbl 1074.68653 · doi:10.1142/S0218195901000444
[17] Wagner, F., Wolff, A., Kapoor, V., Strijk, T.: Three rules suffice for good label placement. Algorithmica 30(2), 334–349 (2001) · Zbl 0984.65015 · doi:10.1007/s00453-001-0009-7
[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)
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.