×

Edge routing with ordered bundles. (English) Zbl 1356.68162

Summary: Edge bundling reduces the visual clutter in a drawing of a graph by uniting the edges into bundles. We propose a method of edge bundling that draws each edge of a bundle separately as in metro-maps and call our method ordered bundles. To produce aesthetically looking edge routes, it minimizes a cost function on the edges. The cost function depends on the ink, required to draw the edges, the edge lengths, widths and separations. The cost also penalizes for too many edges passing through narrow channels by using the constrained Delaunay triangulation. The method avoids unnecessary edge-node and edge-edge crossings. To draw edges with the minimal number of crossings and separately within the same bundle, we develop an efficient algorithm solving a variant of the metro-line crossing minimization problem. In general, the method creates clear and smooth edge routes giving an overview of the global graph structure, while still drawing each edge separately and thus enabling local analysis.

MSC:

68R10 Graph theory (including graph drawing) in computer science
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Argyriou, E.; Bekos, M. A.; Kaufmann, M.; Symvonis, A., Two polynomial time algorithms for the metro-line crossing minimization problem, (Tollis, I. G.; Patrignani, M., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 5417 (2009), Springer), 336-347 · Zbl 1213.68647
[2] Asquith, M.; Gudmundsson, J.; Merrick, D., An ILP for the metro-line crossing problem, (Harland, J.; Manyem, P., Symposium on Computing: The Australasian Theory. Symposium on Computing: The Australasian Theory, CRPIT, vol. 77 (2008), Australian Computer Society), 49-56
[3] Bar, M.; Neta, M., Humans prefer curved visual objects, Psychol. Sci., 17, 8, 645-648 (2006)
[4] Bekos, M. A.; Kaufmann, M.; Potika, K.; Symvonis, A., Line crossing minimization on metro maps, (Hong, S.-H.; Nishizeki, T.; Quan, W., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 4875 (2008), Springer), 231-242 · Zbl 1137.68467
[5] Benkert, M.; Nöllenburg, M.; Uno, T.; Wolff, A., Minimizing intra-edge crossings in wiring diagrams and public transportation maps, (Kaufmann, M.; Wagner, D., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 4372 (2007), Springer), 270-281 · Zbl 1185.68459
[6] Bereg, S.; Holroyd, A. E.; Nachmanson, L.; Pupyrev, S., Drawing permutations with few corners, (Wismath, S. K.; Wolff, A., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 8242 (2013), Springer), 484-495 · Zbl 1406.68064
[7] Cermák, M.; Dokulil, J.; Katreniaková, J., Edge routing and bundling for graphs with fixed node positions, (International Conference on Information Visualisation (2011), IEEE Computer Society), 475-481
[8] Chen, H.-F. S.; Lee, D. T., On crossing minimization problem, IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 17, 5, 406-418 (1998)
[9] Clarkson, K., Approximation algorithms for shortest path motion planning (extended abstract), (Aho, A. V., Symposium on Theory of Computing (1987), ACM), 56-65
[10] Cole, R.; Siegel, A., River routing every which way, but loose (extended abstract), (Symposium on Foundations of Computer Science (1984), IEEE Computer Society), 65-73
[11] Cui, W.; Zhou, H.; Qu, H.; Wong, P. C.; Li, X., Geometry-based edge clustering for graph visualization, IEEE Trans. Vis. Comput. Graph., 14, 6, 1277-1284 (2008)
[12] Dai, W. W.-M.; Dayan, T.; Staepelaere, D., Topological routing in SURF: generating a rubber-band sketch, (ACM/IEEE Design Automation Conference (1991), ACM: ACM New York, NY, USA), 39-44
[13] Dickerson, M.; Eppstein, D.; Goodrich, M. T.; Meng, J. Y., Confluent drawings: visualizing non-planar diagrams in a planar way, J. Graph Algorithms Appl., 9, 1, 31-52 (2005) · Zbl 1086.05022
[14] Dobkin, D.; Gansner, E.; Koutsofios, E.; North, S., Implementing a general-purpose edge router, (Battista, G. D., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 1353 (1997), Springer), 262-271
[15] Domiter, V.; Zalik, B., Sweep-line algorithm for constrained Delaunay triangulation, Int. J. Geogr. Inf. Sci., 22, 4, 449-462 (2008)
[16] Dwyer, T.; Marriott, K.; Wybrow, M., Integrating edge routing into force-directed layout, (Kaufmann, M.; Wagner, D., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 4372 (2007), Springer), 8-19 · Zbl 1185.68471
[17] Dwyer, T.; Nachmanson, L., Fast edge-routing for large graphs, (Eppstein, D.; Gansner, E. R., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 5849 (2009), Springer), 147-158 · Zbl 1284.68458
[18] Eppstein, D.; Goodrich, M. T.; Meng, J. Y., Confluent layered drawings, Algorithmica, 47, 4, 439-452 (2007) · Zbl 1118.68103
[19] Ersoy, O.; Hurter, C.; Paulovich, F. V.; Cantareiro, G.; Telea, A., Skeleton-based edge bundling for graph visualization, IEEE Trans. Vis. Comput. Graph., 17, 12, 2364-2373 (2011)
[20] Fink, M.; Haverkort, H.; Nöllenburg, M.; Roberts, M.; Schuhmann, J.; Wolff, A., Drawing metro maps using Bézier curves, (Didimo, W.; Patrignani, M., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 7704 (2013), Springer), 463-474 · Zbl 1377.68274
[21] Fink, M.; Pupyrev, S., Metro-line crossing minimization: hardness, approximations, and tractable cases, (Wismath, S. K.; Wolff, A., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 8242 (2013), Springer), 328-339 · Zbl 1406.68076
[22] Fink, M.; Pupyrev, S., Ordering metro lines by block crossings, (Chatterjee, K.; Sgall, J., Mathematical Foundations of Computer Science. Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, vol. 8087 (2013), Springer), 397-408 · Zbl 1398.68395
[23] Gansner, E.; Hu, Y.; North, S.; Scheidegger, C., Multilevel agglomerative edge bundling for visualizing large graphs, (Battista, G. D.; Fekete, J.-D.; Qu, H., Pacific Visualization Symposium (2011), IEEE), 187-194
[24] Gansner, E. R.; Koren, Y., Improved circular layouts, (Kaufmann, M.; Wagner, D., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 4372 (2006), Springer), 386-398 · Zbl 1185.68479
[25] Garey, M. R.; Johnson, D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness (1979), W.H. Freeman and Company: W.H. Freeman and Company New York, NY · Zbl 0411.68039
[26] Groeneveld, P., Wire ordering for detailed routing, IEEE Des. Test Comput., 6, 6-17 (1989)
[27] Guttman, A., R-trees: a dynamic index structure for spatial searching, (Yormark, B., International Conference on Management of Data (1984), ACM Press), 47-57, SIGMOD Record 14(2)
[28] Holten, D., Hierarchical edge bundles: visualization of adjacency relations in hierarchical data, IEEE Trans. Vis. Comput. Graph., 12, 5, 741-748 (2006)
[29] Holten, D.; van Wijk, J. J., Force-directed edge bundling for graph visualization, Comput. Graph. Forum, 28, 3, 983-990 (2009)
[30] Hurter, C.; Ersoy, O.; Telea, A., Graph bundling by kernel density estimation, (Computer Graphics Forum, vol. 31 (2012), Wiley Online Library), 865-874
[31] Lambert, A.; Bourqui, R.; Auber, D., Winding roads: routing edges into bundles, Comput. Graph. Forum, 29, 3, 853-862 (2010)
[32] Marek-Sadowska, M.; Sarrafzadeh, M., The crossing distribution problem [IC layout], IEEE Trans. Comput.-Aided Des. Integr. Circuits Syst., 14, 4, 423-433 (1995)
[33] Middendorf, M.; Pfeiffer, F., On the complexity of the disjoint paths problems, Combinatorica, 13, 1, 97-107 (1993) · Zbl 0770.68072
[34] Nachmanson, L.; Robertson, G.; Lee, B., Drawing graphs with GLEE, (Hong, S.-H.; Nishizeki, T.; Quan, W., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 4875 (2007), Springer), 389-394 · Zbl 1137.68500
[35] Newbery, F. J., Edge concentration: a method for clustering directed graphs, (International Workshop on Software Configuration Management (1989)), 76-85
[36] Nöllenburg, M., An improved algorithm for the metro-line crossing minimization problem, (Eppstein, D.; Gansner, E. R., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 5849 (2009), Springer), 381-392 · Zbl 1284.68472
[37] Piegl, L. A.; Tiller, W., Biarc approximation of NURBS curves, Comput. Aided Des., 34, 11, 807-814 (2002)
[38] Pupyrev, S.; Nachmanson, L.; Bereg, S.; Holroyd, A. E., Edge routing with ordered bundles, (van Kreveld, M. J.; Speckmann, B., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 7034 (2012), Springer), 136-147 · Zbl 1311.68124
[39] Pupyrev, S.; Nachmanson, L.; Kaufmann, M., Improving layered graph layouts with edge bundling, (Brandes, U.; Cornelsen, S., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 6502 (2010), Springer), 465-479
[40] Purchase, H. C.; Hamer, J.; Nöllenburg, M.; Kobourov, S. G., On the usability of Lombardi graph drawings, (Didimo, W.; Patrignani, M., International Symposium on Graph Drawing. International Symposium on Graph Drawing, Lecture Notes in Computer Science, vol. 7704 (2013), Springer), 451-462 · Zbl 1377.68185
[41] Wein, R.; van den Berg, J.; Halperin, D., The visibility-Voronoi complex and its applications, Comput. Geom. Theory Appl., 36, 1, 66-87 (2007) · Zbl 1110.65021
[42] Xu, K.; Rooney, C.; Passmore, P.; Ham, D.-H.; Nguyen, P. H., A user study on curved edges in graph visualization, IEEE Trans. Vis. Comput. Graph., 18, 12, 2449-2456 (2012)
[43] Yao, A. C.-C., On constructing minimum spanning trees in k-dimensional spaces and related problems, SIAM J. Comput., 11, 4, 721-736 (1982) · Zbl 0492.68050
[44] Gephi dataset
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.