A survey of direction-preserving layout strategies

ABSTRACT

In this paper we analyze different layout algorithms that preserve relative directions in geo-referenced networks. This is an important criterion for many sensor networks such as the electric grid and other supply networks, because it enables the user to match the geographic setting with the drawing on the screen. Even today, the layout of these networks are often created manually. This is due to the requirement that these layouts must respect geographic references but should still be easy to read and understand. The range of available automatic algorithms spans from general graph layouts over schematic maps to semi-realistic drawings. At first sight, schematics seem to be a promising compromise between geographic correctness and readability. The former property exploits the mental map of the user while the latter makes it easier for the user to learn about the network structure. We investigate different algorithms for such maps together with different visualization techniques.

In particular, the group of octi-linear layouts is prominent in handcrafted subway maps. These algorithms have been used extensively to generate drawings for subway maps. Also known as Metro Map layouts, only horizontal, vertical and diagonal directions are allowed. This increases flexibility and makes the resulting layout look similar to the well-known subway maps of large cities. The key difference to general graph layout algorithms is that geographic relations are respected in terms of relative directions.

However, it is not clear, whether this metaphor can be transferred from metro maps to other domains. We discuss applicability of these different approaches for geo-based networks in general with the electric grid as a use-case scenario.

References

1. Avelar, S., and Müller, M. 2000. Generating topologically correct schematic maps. In Proceedings of the 9th International Symposium on Spatial Data Handling, 4--28.
2. Barkowsky, T., Latecki, L. J., and Richter, K.-F. 2000. Schematizing maps: Simplification of geographic shape by discrete curve evolution. In Spatial Cognition II, vol. 1849 of Lecture Notes in Computer Science. Springer, Heidelberg, 41--53.
3. Bekos, M. A., Kaufmann, M., Symvonis, A., and Wolff, A. 2007. Boundary labeling: Models and efficient algorithms for rectangular maps. Computational Geometry 36, 3, 215--236.
4. Böttger, J., Brandes, U., Deussen, O., and Ziezold, H. 2008. Map warping for the annotation of metro maps. Computer Graphics and Applications, IEEE 28, 5, 56--65.
5. Cabello, S., and Kreveld, M. 2003. Approximation algorithms for aligning points. Algorithmica 37, 3, 211--232.
6. Cabello, S., de Berg, M., van Dijk, S., van Kreveld, M., and Strijk, T. 2001. Schematization of road networks. In Proceedings of the Seventeenth Annual Symposium on Computational Geometry, ACM, New York, NY, USA, SCG '01, 33--39.
7. Cabello, S., de Berg, M., and van Kreveld, M. 2005. Schematization of networks. Computational Geometry 30, 3, 223--238.
8. Carpendale, M., Cowperthwaite, D., and Fracchia, F. 1997. Extending distortion viewing from 2d to 3d. Computer Graphics and Applications 17, 4, 42--51.
9. do Nascimento, H. A., and Eades, P. 2008. User hints for map labeling. Journal of Visual Languages & Computing 19, 1, 39--74. Spatial and Image-based Information Systems.
10. Dwyer, T., Lee, B., Fisher, D., Quinn, K., Isenberg, P., Robertson, G., and North, C. 2009. A comparison of user-generated and automatic graph layouts. Visualization and Computer Graphics, IEEE Transactions on 15, 6, 961--968.
11. Eiglsperger, M., Fekete, S. P., and Klau, G. W. 2001. Orthogonal graph drawing. In Drawing Graphs, M. Kaufmann and D. Wagner, Eds., vol. 2025 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 121--171.
12. Fekete, J.-D., and Plaisant, C. 1999. Excentric labeling: Dynamic neighborhood labeling for data visualization. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, ACM, New York, NY, USA, CHI '99, 512--519.
13. Fink, M., Haverkort, H., Nllenburg, M., Roberts, M., Schuhmann, J., and Wolff, A. 2013. Drawing metro maps using bézier curves. In Graph Drawing, W. Didimo and M. Patrignani, Eds., vol. 7704 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 463--474.
14. Garland, K., and Beck, H. C. 1994. Mr Beck's Underground Map. Capital Transport.
15. Hadlak, S., Schulz, H.-J., and Schumann, H. 2011. In situ exploration of large dynamic networks. IEEE Transactions on Visualization and Computer Graphics 17, 12, 2334--2343.
16. Haunert, J.-H., and Sering, L. 2011. Drawing road networks with focus regions. IEEE Transactions on Visualization and Computer Graphics 17, 12, 2555--2562.
17. Hong, S.-H., Merrick, D., and Nascimento, H. 2005. The metro map layout problem. In Graph Drawing, J. Pach, Ed., vol. 3383 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 482--491.
18. Hong, S.-H., Merrick, D., and do Nascimento, H. A. 2006. Automatic visualisation of metro maps. Journal of Visual Languages & Computing 17, 3, 203--224.
19. Imhof, E. 1975. Positioning names on maps. The American Cartographer 2, 2, 128--144.
20. Kaufmann, M., and Wagner, D. 2001. Drawing Graphs: Methods and Models, vol. 2025. Springer.
21. Klump, R., Schooley, D., and Overbye, T. 2002. An advanced visualization platform for real-time power system operations. In Proc. of the 14th Power Systems Computation Conference.
22. May, T., Steiger, M., Davey, J., and Kohlhammer, J. 2012. Using signposts for navigation in large graphs. Computer Graphics Forum 31, 3pt2, 985--994.
23. Merrick, D., and Gudmundsson, J. 2007. Path simplification for metro map layout. In Graph Drawing, M. Kaufmann and D. Wagner, Eds., vol. 4372 of Lecture Notes in Computer Science. Springer, Heidelberg, 258--269.
24. Mittelstädt, S., Spretke, D., Sacha, D., Keim, D. A., Heyder, B., and Kopp, J. 2013. Visual analytics for critical infrastructures. In Security in Critical Infrastructures Today, Proc. of Int. ETG-Congress; Symposium 1, 1--8.
25. Morrison, A. 1996. Public transport maps in western european cities. The Cartographic Journal 33, 2, 93--110.
26. Nesbitt, K. 2004. Getting to more abstract places using the metro map metaphor. In Information Visualisation, 2004. IV 2004. Proceedings. Eighth International Conference on, 488--493.
27. Neumayer, R., Mayer, R., Pölzlbauer, G., and Rauber, A. 2007. The metro visualisation of component planes for self-organising maps. In International Joint Conference on Neural Networks, 2788--2793.
28. Nöllenburg, M., and Wolff, A. 2006. A mixed-integer program for drawing high-quality metro maps. In Graph Drawing, P. Healy and N. Nikolov, Eds., vol. 3843 of Lecture Notes in Computer Science. Springer Berlin Heidelberg, 321--333.
29. Nöllenburg, M., and Wolff, A. 2011. Drawing and labeling high-quality metro maps by mixed-integer programming. IEEE Transactions on Vis. and CG. 17, 5, 626--641.
30. Nöllenburg, M. 2005. Automated drawing of metro maps. Master's thesis, Universität Karlsruhe, Fakultät für Informatik.
31. Ovenden, M. 2005. Metro maps of the world. Capital Transport.
32. Overbye, T. J., Weber, J. D., and Laufenberg, M. 1999. Visualization of flows and transfer capability in electric networks. Proceedings of the 13th Power System Computation Conference 51 (June), 420--426.
33. Overbye, T., Meliopoulos, A., Wiegmann, D., and Cokkinides, G. 2005. Visualization of power systems and components. Tech. rep., Power Systems Engineering Research Center(PSERC).
34. Reilly, D. F., and Inkpen, K. M. 2004. Map morphing: Making sense of incongruent maps. In Proceedings of Graphics Interface 2004, Canadian Human-Computer Communications Society, 231--238.
35. Reilly, D. F., and Inkpen, K. M. 2007. White rooms and morphing don't mix: Setting and the evaluation of visualization techniques. In Proceedings of the SIGCHI Conference on Human Factors in Computing Systems, ACM, New York, NY, USA, CHI '07, 111--120.
36. Roberts, M. J., Newton, E. J., Lagattolla, F. D., Hughes, S., and Hasler, M. C. 2013. Objective versus subjective measures of paris metro map usability: Investigating traditional octolinear versus all-curves schematics. International Journal of Human-Computer Studies 71, 3, 363--386.
37. Roberts, M. J. 2012. Underground maps unravelled: Explorations in information design. Maxwell J. Roberts.
38. Shahaf, D., Guestrin, C., and Horvitz, E. 2012. Metro maps of science. In Proceedings of the 18th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ACM, New York, NY, USA, KDD '12, 1122--1130.
39. Stott, J. M., and Rodgers, P. 2005. Automatic metro map design techniques. In Proceedings of the 22nd International Cartographic Conference.
40. Stott, J., Rodgers, P., Martínez-Ovando, J., and Walker, S. 2011. Automatic metro map layout using multicriteria optimization. IEEE Transactions on Vis. and CG. 17, 1, 101--114.
41. Sun, Y., and Overbye, T. J. 2004. Visualizations for power system contingency analysis data. Power Systems, IEEE Transactions on 19, 4, 1859--1866.
42. Tamassia, R. 1987. On embedding a graph in the grid with the minimum number of bends. SIAM Journal on Computing 16, 3, 421--444.
43. Tollis, I. G., Battista, G. D., Eades, P., and Tamassia, R. 1998. Graph Drawing: Algorithms for the Visualization of Graphs, vol. 1. Prentice Hall, New York.
44. Tufte, E. R. 1997. Visual explanations: images and quantities, evidence and narrative, vol. 107. Graphics Press Cheshire, CT.
45. Wang, Y.-S., and Chi, M.-T. 2011. Focus+context metro maps. IEEE Transactions on Visualization and Computer Graphics 17, 12, 2528--2535.
46. Ware, J. M., Taylor, G. E., Anand, S., and Thomas, N. 2006. Automated production of schematic maps for mobile applications. Transactions in GIS 10, 1, 25--42.
47. Wolff, A. 2007. Drawing subway maps: A survey. Informatik - Forschung und Entwicklung 22, 1, 23--44.
48. Wong, P. C., Schneider, K., Mackey, P., Foote, H., Chin, G., Guttromson, R., and Thomas, J. 2009. A novel visualization technique for electric power grid analytics. Visualization and Computer Graphics, IEEE Transactions on 15, 3, 410--423.
49. Wu, H.-Y., Takahashi, S., Hirono, D., Arikawa, M., Lin, C.-C., and Yen, H.-C. 2013. Spatially efficient design of annotated metro maps. CG. Forum 32, 3pt3, 261--270.

Index Terms

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction devices

      • Touch screens

  • Interaction design

• Information systems

  • Data management systems

    • Data structures

  • Information storage systems

    • Record storage systems

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features

        • Data types and structures

• Theory of computation

  • Design and analysis of algorithms

    • Data structures design and analysis

  • Theory and algorithms for application domains

    • Database theory

      • Data structures and algorithms for data management