A spatial one-to-many flow layout algorithm using triangulation, approximate Steiner trees, and path smoothing

References

• Andrienko, G., Andrienko, N., Dykes, J., Fabrikant, S. I., & Wachowicz, M. (2008). Geovisualization of dynamics, movement and change: Key issues and developing approaches in visualization research. Information Visualization, 7(3–4), 173–180. doi:10.1057/IVS.2008.23
   Web of Science ®Google Scholar
• Andrienko, N., & Andrienko, G. (2013). Visual analytics of movement: An overview of methods, tools and procedures. Information Visualization, 12(1), 3–24. doi:10.1177/1473871612457601
   Web of Science ®Google Scholar
• Beecham, R., & Wood, J. (2014). Characterising group-cycling journeys using interactive graphics. Transportation Research Part C: Emerging Technologies, 47, 194–206. doi:10.1016/j.trc.2014.03.007
   Web of Science ®Google Scholar
• Bennett, C., Ryall, J., Spalteholz, L., & Gooch, A. (2007). The aesthetics of graph visualization. In D. W. Cunningham, G. Meyer, & L. Neumann (Eds), Computational Aesthetics'07: Proceedings of the Third Eurographics conference on Computational Aesthetics in Graphics, Visualization and Imaging (pp. 57–74). Aire-la-Ville, Switzerland: Eurographics Association. doi:10.2312/COMPAESTH/COMPAESTH07/057-064
   Google Scholar
• Boyandin, I., Bertini, E., Bak, P., & Lalanne, D. (2011). Flowstrates: An approach for visual exploration of temporal origin-destination data. Computer Graphics Forum, 30(3), 971–980. doi:10.1111/cgf.2011.30.issue-3
   Web of Science ®Google Scholar
• Buchin, K., Speckmann, B., & Verbeek, K. (2011). Flow map layout via spiral trees. IEEE Transactions on Visualization and Computer Graphics, 17(12), 2536–2544. doi:10.1109/TVCG.2011.202
   PubMed Web of Science ®Google Scholar
• Buchin, K., Speckmann, B., & Verbeek, K. (2015). Angle-restricted Steiner arborescences for flow map layout. Algorithmica, 72(2), 656–685. doi:10.1007/s00453-013-9867-z
   Web of Science ®Google Scholar
• Census, U. S. 2003. State of residence in 2000 for the population 5 years and over by state of residence in 1995 [cited 2003, June 08]. Available from https://www.census.gov/population/www/cen2000/briefs/phc-t22/index.html.
   Google Scholar
• Chrisman, N. (1999). A transformational approach to GIS operations. International Journal of Geographical Information Science, 13(7), 617–637. doi:10.1080/136588199241030
   Web of Science ®Google Scholar
• Claudel, M., Nagel, T., & Ratti, C. (2016). From origins to destinations: The past, present and future of visualizing flow maps. Built Environment, 42(3), 338–355. doi:10.2148/benv.42.3.338
   Google Scholar
• Debiasi, A., Simões, B., & De Amicis, R. (2014). Supervised force directed algorithm for the generation of flow maps. In WSCG 2014 Conference on Computer Graphics, Visualization and Computer Vision (pp. 193–202). Plzen, Czech Republic: Václav Skala - UNION Agency.
   Google Scholar
• Dorigo, M., Birattari, M., & Stutzle, T. (2006). Ant colony optimization. IEEE Computational Intelligence Magazine, 1(4), 28–39. doi:10.1109/MCI.2006.329691
   Web of Science ®Google Scholar
• Food and Agriculture Organization of the United Nations. 2018. FAOSTAT: Detailed trade matrix 2018 [cited 2018, September01]. Available from www.fao.org/faostat/en/#data/TM.
   Google Scholar
• Friendly, M. (2000). Re-visions of Minard. Statistical Computing & Statistical Graphics Newsletter, 11(1), 1.
   Google Scholar
• Garey, M. R., Graham, R. L., & Johnson, D. S. (1976). Some Np-complete geometric problems. In STOC '76 Proceedings of the eighth annual ACM symposium on Theory of computing (pp. 10–22). New York: ACM. doi:10.1145/800113.803626.
   Google Scholar
• Ghoniem, M., Fekete, J.-D., & Castagliola, P. (2005). On the readability of graphs using node-link and matrix-based representations: A controlled experiment and statistical analysis. Information Visualization, 4(2), 114–135. doi:10.1057/palgrave.ivs.9500092
   Google Scholar
• Goodchild, M. F., Yuan, M., & Cova, T. J. (2007). Towards a general theory of geographic representation in GIS. International Journal of Geographical Information Science, 21(3), 239–260. doi:10.1080/13658810600965271
   Web of Science ®Google Scholar
• Guo, D. (2009). Flow mapping and multivariate visualization of large spatial interaction data. IEEE Transactions on Visualization and Computer Graphics, 15(6), 1041–1048. doi:10.1109/TVCG.2009.143
   PubMed Web of Science ®Google Scholar
• Guo, D., & Zhu, X. (2014). Origin-destination flow data smoothing and mapping. IEEE Transactions on Visualization and Computer Graphics, 20(12), 2043–2052. doi:10.1109/TVCG.2014.2346271
   PubMed Web of Science ®Google Scholar
• Holten, D., & Van Wijk, J. J. (2009). Force-directed edge bundling for graph visualization. Computer Graphics Forum, 28(3), 983–990. doi:10.1111/j.1467-8659.2009.01450.x
   Web of Science ®Google Scholar
• Hwang, F. K., & Richards, D. S. (1992). Steiner tree problems. Networks, 22(1), 55–89. doi:10.1002/net.3230220105
   Web of Science ®Google Scholar
• Jenny, B., Stephen, D. M., Muehlenhaus, I., Marston, B. E., Sharma, R., Zhang, E., & Jenny, H. (2017). Force-directed layout of origin-destination flow maps. International Journal of Geographical Information Science, 31(8), 1521–1540. doi:10.1080/13658816.2017.1307378
   Web of Science ®Google Scholar
• Jenny, B., Stephen, D. M., Muehlenhaus, I., Marston, B. E., Sharma, R., Zhang, E., & Jenny, H. (2018). Design principles for origin-destination flow maps. Cartography and Geographic Information Science, 45(1), 62–75. doi:10.1080/15230406.2016.1262280
   PubMed Web of Science ®Google Scholar
• Kim, K., Lee, S.-I., Shin, J., & Choi, E. (2012). Developing a flow mapping module in a GIS environment. The Cartographic Journal, 49(2), 164–175. doi:10.1179/174327711X13166800242356
   Web of Science ®Google Scholar
• Kou, L., Markowsky, G., & Berman, L. (1981). A fast algorithm for Steiner trees. Acta Informatica, 15(2), 141–145. doi:10.1007/BF00288961
   Web of Science ®Google Scholar
• Koylu, C., & Guo, D. (2017). Design and evaluation of line symbolizations for origin–destination flow maps. Information Visualization, 16(4), 309–331. doi:10.1177/1473871616681375
   Web of Science ®Google Scholar
• Kraak, M. J. (2014). Mapping time: Illustrated by Minard’s map of Napoleon’s Russian campaign of 1812. Redlands, CA: Esri Press.
   Google Scholar
• von Landesberger, T. V., Brodkorb, F., Roskosch, P., Andrienko, N., Andrienko, G., & Kerren, A. (2016). MobilityGraphs: Visual analysis of mass mobility dynamics via spatio-temporal graphs and clustering. IEEE Transactions on Visualization and Computer Graphics, 22(1), 11–20. doi:10.1109/TVCG.2015.2468111
   PubMed Web of Science ®Google Scholar
• Liu, L. (1995). PPFLOW: An interactive visualization system for the exploratory analysis of migration flows. Geographic Information Sciences, 1(2), 118–123. doi:10.1080/10824009509480477
   Google Scholar
• Long, J. A., & Nelson, T. A. (2013). A review of quantitative methods for movement data. International Journal of Geographical Information Science, 27(2), 292–318. doi:10.1080/13658816.2012.682578
   Web of Science ®Google Scholar
• MacDonald, G. K., Brauman, K. A., Sun, S., Carlson, K. M., Cassidy, E. S., Gerber, J. S., & West, P. C. (2015). Rethinking agricultural trade relationships in an era of globalization. BioScience, 65(3), 275–289. doi:10.1093/biosci/biu225
   Web of Science ®Google Scholar
• Marble, D. F., Gou, Z., Liu, L., & Saunders, J. (1997). Recent advances in the exploratory analysis of interregional flows in space and time. In Z. Kemp (Ed), Innovations in GIS 4: Selected papers from the Fourth National Conference on GIS Research UK (GISRUK) (pp. 75–81). London: Taylor & Francis.
   Google Scholar
• Nocaj, A., & Brandes, U. (2013). Stub bundling and confluent spirals for geographic networks in S. Wismath, & A. Wolff (Eds) Graph Drawing. GD 2013. Lecture Notes in Computer Science, vol 8242 (pp. 388–399). Cham, Switzerland: Springer International. doi:10.1007/978-3-319-03841-4_34.
   Google Scholar
• Phan, D., Xiao, L., Yeh, R., & Hanrahan, P. (2005). Flow map layout. In J. Stasko, & M. Ward (Eds), IEEE Symposium on Information Visualization (InfoVis 05), Proceedings (pp. 219–254). Piscataway, NJ: IEEE. doi 10.1109/INFVIS.2005.1532150
   Google Scholar
• Rabanal, P., Rodríguez, I., & Rubio, F. (2007). Using river formation dynamics to design heuristic algorithms. In S. G. Akl, C. S. Calude, M. J. Dinneen, G. Rozenberg, & H. T. Wareham (Eds), UC'07 Proceedings of the 6th international conference on Unconventional Computation (pp. 163–177). Berlin: Springer. doi:10.1007/978-3-540-73554-0_16.
   Google Scholar
• Robins, G., & Zelikovsky, A. (2000). Improved Steiner tree approximation in graphs. In SODA ’00 Proceedings of the eleventh annual ACM-SIAM symposium on Discrete algorithms (pp. 770–779). Philadelphia: Society for Industrial and Applied Mathematics.
   Google Scholar
• Robinson, A. H. (1967). The thematic maps of Charles Joseph Minard. Imago Mundi, 21(1), 95–108. doi:10.1080/03085696708592302
   Google Scholar
• Sander, N., Abel, G. J., Bauer, R., & Schmidt, J. (2014). Visualising migration flow data with circular plots (Vienna Institute of Demography Working Papers, No. 2/2014). Retrieved from http://hdl.handle.net/10419/97018.
   Google Scholar
• Smith, R. H. (1970). Concepts and methods in commodity flow analysis. Economic Geography, 46(sup1), 404–416. doi:10.2307/143153
   Web of Science ®Google Scholar
• Stephen, D. M., & Jenny, B. (2017). Automated layout of origin–destination flow maps: US county-to-county migration 2009–2013. Journal of Maps, 13(1), 46–55. doi:10.1080/17445647.2017.1313788
   Web of Science ®Google Scholar
• Sun, S. (2016, September). An automated spatial flow layout algorithm using triangulation, approximate Steiner tree, and path smoothing. Paper read at AutoCarto 2016: The 21st International Research Symposium on Computer-based Cartography and GIScience, Albuquerque, NM. Retrieved from http://www.cartogis.org/docs/proceedings/2016/Sun.pdf.
   Google Scholar
• Sun, S., & Manson, S. (2012). Intraurban migration, neighborhoods, and city structure. Urban Geography, 33(7), 1008–1029. doi:10.2747/0272-3638.33.7.1008
   Web of Science ®Google Scholar
• Tao, R., & Thill, J. C. (2016). Spatial cluster detection in spatial flow data. Geographical Analysis, 48(4), 355–372. doi:10.1111/gean.12100
   Web of Science ®Google Scholar
• Thompson, W., & Lavin, S. (1996). Automatic generation of animated migration maps. Cartographica: The International Journal for Geographic Information and Geovisualization, 33(2), 17–28. doi:10.3138/P4Q4-1220-3774-M430
   Google Scholar
• Tobler, W. R. (1987). Experiments in migration mapping by computer. The American Cartographer, 14(2), 155–163. doi:10.1559/152304087783875273
   Web of Science ®Google Scholar
• Ware, C., Purchase, H., Colpoys, L., & McGill, M. (2002). Cognitive measurements of graph aesthetics. Information Visualization, 1(2), 103–110. doi:10.1057/palgrave.ivs.9500013
   Google Scholar
• Wheeler, A. (2015). Visualization techniques for journey to crime flow data. Cartography and Geographic Information Science, 42(2), 149–161. doi:10.1080/15230406.2014.890545
   Web of Science ®Google Scholar
• Wood, J., Dykes, J., & Slingsby, A. (2010). Visualisation of origins, destinations and flows with OD maps. The Cartographic Journal, 47(2), 117–129. doi:10.1179/000870410X12658023467367
   Web of Science ®Google Scholar
• Xiao, N., & Chun, Y. (2009). Visualizing migration flows using kriskograms. Cartography and Geographic Information Science, 36(2), 183–191. doi:10.1559/152304009788188763
   Web of Science ®Google Scholar
• Yang, X.-S. (2010). Nature-inspired metaheuristic algorithms. Frome, UK: Luniver press.
   Google Scholar
• Yang, Y., Dwyer, T., Goodwin, S., & Marriott, K. (2017). Many-to-many geographically-embedded flow visualisation: An evaluation. IEEE Transactions on Visualization and Computer Graphics, 23(1), 411–420. doi:10.1109/TVCG.2016.2598885
   PubMed Web of Science ®Google Scholar
• Yattaw, N. J. (1999). Conceptualizing space and time: A classification of geographic movement. Cartography and Geographic Information Science, 26(2), 85–98. doi:10.1559/152304099782330734
   Google Scholar
• Zhou, H., Xu, P., Yuan, X., & Qu, H. (2013). Edge bundling in information visualization. Tsinghua Science and Technology, 18(2), 145–156. doi:10.1109/TST.2013.6509098
   Web of Science ®Google Scholar
• Zhu, X., & Guo, D. (2014). Mapping large spatial flow data with hierarchical clustering. Transactions in GIS, 18(3), 421–435. doi:10.1111/tgis.12100
   Web of Science ®Google Scholar