Data-driven graph drawing techniques with applications for conveyor systems. (English) Zbl 1507.68227
Summary: The visualization of conveyor systems in the sense of a connected graph is a challenging problem. Starting from communication data provided by the IT system, graph drawing techniques are applied to generate an appealing layout of the conveyor system. From a mathematical point of view, the key idea is to use the concept of stress majorization to minimize a stress function over the positions of the nodes in the graph. Different to the already existing literature, we have to take care of special features inspired by the real-world problems.
MSC:
| 68R10 | Graph theory (including graph drawing) in computer science |
| 90B30 | Production models |
| 90C35 | Programming involving graphs or networks |
Software:
SparseMatrixReferences:
| [1] | Asarnow, D.; Singh, R., The impact of structural diversity and parameterization on maps of the protein universe, BMC Proc, 7, 1-10 (2013) · doi:10.1186/1753-6561-7-S7-S1 |
| [2] | Bergmann, S.; Strassburger, S., Challenges for the automatic generation of simulation models for production systems, Proceedings of the 2010 summer computer simulation conference, SCSC’10, 545-549 (2010), San Diego: Society for Computer Simulation International, San Diego |
| [3] | Bleifuss, R.; Spieckermann, S.; Stauber, S., A case study on simulation and emulation of a new case picking system for a us based wholesaler, Proceedings of the 2012 winter simulation conference (WSC), 1-12 (2012) |
| [4] | Borg, I.; Groenen, PJ; Mair, P., Applied multidimensional scaling and unfolding (2018), Cham: Springer, Cham · Zbl 1409.62006 · doi:10.1007/978-3-319-73471-2 |
| [5] | Brandes, U.; Pich, C.; Kaufmann, M.; Wagner, D., Eigensolver methods for progressive multidimensional scaling of large data, Graph drawing, 42-53 (2007), Berlin: Springer, Berlin · Zbl 1185.68847 · doi:10.1007/978-3-540-70904-6_6 |
| [6] | Brandes, U.; Pich, C.; Tollis, IG; Patrignani, M., An experimental study on distance-based graph drawing, Graph drawing, 218-229 (2009), Berlin: Springer, Berlin · Zbl 1213.68429 · doi:10.1007/978-3-642-00219-9_21 |
| [7] | Chen, C., Information visualization: beyond the horizon (2006), London: Springer, London |
| [8] | Davis, TA; Hu, Y., The university of Florida sparse matrix collection, ACM Trans Math Softw, 38, 1:1-1:25 (2011) · Zbl 1365.65123 |
| [9] | De Leeuw, J., Convergence of the majorization method for multidimensional scaling, J Classif, 5, 163-180 (1988) · Zbl 0692.62056 · doi:10.1007/BF01897162 |
| [10] | Di, G., Battista, graph drawing: algorithms for the visualization of graphs, an Alan R. Apt book (1999), Upper Saddle River: Prentice Hall, Upper Saddle River · Zbl 1057.68653 |
| [11] | Dwyer, T.; Koren, Y.; Marriott, K.; Healy, P.; Nikolov, NS, Stress majorization with orthogonal ordering constraints, Graph drawing, 141-152 (2005), Berlin: Springer, Berlin · Zbl 1171.68608 |
| [12] | Eades, P.; Wormald, N., Fixed edge-length graph drawing is NP-hard, Discrete Appl Math, 28, 111-134 (1990) · Zbl 0744.05053 · doi:10.1016/0166-218X(90)90110-X |
| [13] | Fáry, I., On straight line representation of planar graphs, Acta Univ Szeged, Sect Sci Math, 11, 229-233 (1948) · Zbl 0030.17902 |
| [14] | Gansner ER, Hu Y, Krishnan S. COAST: A convex optimization approach to stress-based embedding. CoRR 2013. arXiv:1308.5218. · Zbl 1406.68081 |
| [15] | Gansner, ER; Hu, Y.; North, S., A maxent-stress model for graph layout, IEEE Trans Vis Comput Graph, 19, 927-940 (2013) · doi:10.1109/TVCG.2012.299 |
| [16] | Gansner, ER; Koren, Y.; North, S.; Pach, J., Graph drawing by stress majorization, Graph drawing, 239-250 (2004), Berlin: Springer, Berlin · Zbl 1111.68580 |
| [17] | Gellrich, A.; Wagner, T.; Vasyutynskyy, V.; Kabitzsch, K., Modeling of transport times in partly observable factory logistic systems based on event logs, ETFA2011, 1-7 (2011) |
| [18] | Gotsman, C.; Koren, Y.; Pach, J., Distributed graph layout for sensor networks, Graph drawing, 273-284 (2005), Berlin: Springer, Berlin · Zbl 1111.68582 · doi:10.1007/978-3-540-31843-9_28 |
| [19] | Hu, Y.; Shi, L., Visualizing large graphs, Wiley Interdiscip Rev: Comput Stat, 7, 115-136 (2015) · Zbl 07912759 · doi:10.1002/wics.1343 |
| [20] | Kamada, T.; Kawai, S., An algorithm for drawing general undirected graphs, Inf Process Lett, 31, 7-15 (1989) · Zbl 0679.68128 · doi:10.1016/0020-0190(89)90102-6 |
| [21] | Kaufmann, M.; Wagner, D., Drawing graphs methods and models (2001), Berlin: Springer, Berlin · Zbl 0977.68644 · doi:10.1007/3-540-44969-8 |
| [22] | Khoury, M.; Hu, Y.; Krishnan, S.; Scheidegger, C., Drawing large graphs by low-rank stress majorization (2012), Malden: The Eurographics Association and Blackwell Publishing Ltd., Malden |
| [23] | Knuth, DE, Computer-drawn flowcharts, Commun ACM, 6, 555-563 (1963) · doi:10.1145/367593.367620 |
| [24] | Meyerhenke, H.; Nöllenburg, M.; Schulz, C.; Di Giacomo, E.; Lubiw, A., Drawing large graphs by multilevel maxent-stress optimization, Graph drawing and network visualization, 30-43 (2015), Cham: Springer, Cham · Zbl 1471.68206 · doi:10.1007/978-3-319-27261-0_3 |
| [25] | Nawaz, S.; Jha, S., A graph drawing approach to sensor network localization, 2007 IEEE international conference on mobile adhoc and sensor systems, 1-12 (2007) |
| [26] | Ortmann M, Klimenta M, Brandes U. A sparse stress model. CoRR 2016. arXiv:1608.08909. · Zbl 1478.68256 |
| [27] | Pich C. Applications of multidimensional scaling to graph drawing. PhD thesis, Universität Konstanz, Konstanz, 2009. Available at http://nbn-resolving.de/urn:nbn:de:bsz:352-opus-83992, last checked 06.03.2020. |
| [28] | Tutte, WT, How to draw a graph, Proc Lond Math Soc (3), 13, 743-767 (1963) · Zbl 0115.40805 · doi:10.1112/plms/s3-13.1.743 |
| [29] | Wang, Y.; Wang, Z., A fast successive over-relaxation algorithm for force-directed network graph drawing, Sci China Inf Sci, 55, 677-688 (2012) · Zbl 1245.68148 · doi:10.1007/s11432-011-4208-9 |
| [30] | Zheng JX, Pawar S, Goodman DFM. Graph drawing by stochastic gradient descent. CoRR. 2018. arXiv:1710.04626. |
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.
