Abstract
Linear cartograms visualize travel times between locations, usually by deforming the underlying map such that Euclidean distance corresponds to travel time. We introduce an alternative model, where the map and the locations remain fixed, but edges are drawn as sinusoid curves. Now the travel time over a road corresponds to the length of the curve. Of course the curves might intersect if not placed carefully. We study the corresponding algorithmic problem and show that suitable placements can be computed efficiently. However, the problem of placing as many curves as possible in an ideal, centered position is NP-hard. We introduce three heuristics to optimize the number of centered curves and show how to create animated visualizations.
K. Buchin, A. van Goethem, and B. Speckmann are supported by the Netherlands Organisation for Scientific Research (NWO) under project no. 612.001.207 (KB), no. 612.001.102 (AvG), and no. 639.023.208 (BS). M. Hoffmann is partially supported by the ESF EUROCORES programme EuroGIGA, CRP GraDR and SNF Project 20GG21-134306.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Robinson, A., Morrison, J., Muehrcke, P., Kimerling, J., Guptill, S.: Elements of cartography. John Wiley & Sons (1995)
Bies, S., van Kreveld, M.: Time-space maps from triangulations. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 511–516. Springer, Heidelberg (2013)
Cabello, S., Demaine, E., Rote, G.: Planar embeddings of graphs with specified edge lengths. Journal of Graph Algorithms and Applications 11(1), 259–276 (2007)
Kaiser, C., Walsh, F., Farmer, C., Pozdnoukhov, A.: User-centric time-distance representation of road networks. In: Fabrikant, S.I., Reichenbacher, T., van Kreveld, M., Schlieder, C. (eds.) GIScience 2010. LNCS, vol. 6292, pp. 85–99. Springer, Heidelberg (2010)
Shimizu, E., Inoue, R.: A new algorithm for distance cartogram construction. International Journal of Geographical Information Science 23(11), 1453–1470 (2009)
Langlois, P., Denain, J.C.: Cartographie en anamorphose. Cybergeo: European Journal of Geography (1996)
Bouts, Q., Dwyer, T., Dykes, J., Speckmann, B., Riche, N., Carpendale, S., Goodwin, S., Liebman, A.: Visual encoding of dissimilarity data via topology preserving map deformation (in preparation, 2014)
Barequet, G., Goodrich, M., Riley, C.: Drawing planar graphs with large vertices and thick edges. Journal of Graph Algorithms and Applications 8(1), 3–20 (2004)
Goodrich, M., Wagner, C.: A framework for drawing planar graphs with curves and polylines. Journal of Algorithms 37(2), 399–421 (2000)
Efrat, A., Erten, C., Kobourov, S.: Fixed-location circular-arc drawing of planar graphs. Journal of Graph Algorithms and Applications 11(1), 145–164 (2007)
Duncan, C., Eppstein, D., Goodrich, M., Kobourov, S., Nöllenburg, M.: Lombardi drawings of graphs. Journal of Graph Algorithms and Applications 16(1), 37–83 (2012)
Nielsen, C., Jackman, S., Birol, I., Jones, S.: Abyss-explorer: visualizing genome sequence assemblies. IEEE Transactions on Visualization and Computer Graphics 15(6), 881–888 (2009)
Wolff, A., Strijk, T.: The map labeling bibliography (2009), http://liinwww.ira.uka.de/bibliography/Theory/map.labeling.html
Poon, C.K., Zhu, B., Chin, F.: A polynomial time solution for labeling a rectilinear map. Information Processing Letters 65(4), 201–207 (1998)
Strijk, T., van Kreveld, M.: Labeling a rectilinear map more efficiently. Information Processing Letters 69(1), 25–30 (1999)
Saux, E., Daniel, M.: Data reduction of polygonal curves using B-splines. Computer-Aided Design 31(8), 507–515 (1999)
Aspvall, B., Plass, M., Tarjan, R.: A linear-time algorithm for testing the truth of certain quantified boolean formulas. Information Processing Letters 8(3), 121–123 (1979)
Halperin, D.: Arrangements. In: Handbook of Discrete and Computational Geometry. Chapman & Hall/CRC (2004)
Guibas, L., Hershberger, J., Mitchell, J., Snoeyink, J.: Approximating polygons and subdivisions with minimum-link paths. International Journal of Computational Geometry & Applications 3(4), 383–415 (1993)
Fabrikant, S., Montello, D., Ruocco, M., Middleton, R.: The distance–similarity metaphor in network-display spatializations. Cartography and Geographic Information Science 31(4), 237–252 (2004)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Buchin, K., van Goethem, A., Hoffmann, M., van Kreveld, M., Speckmann, B. (2014). Travel-Time Maps: Linear Cartograms with Fixed Vertex Locations. In: Duckham, M., Pebesma, E., Stewart, K., Frank, A.U. (eds) Geographic Information Science. GIScience 2014. Lecture Notes in Computer Science, vol 8728. Springer, Cham. https://doi.org/10.1007/978-3-319-11593-1_2
Download citation
DOI: https://doi.org/10.1007/978-3-319-11593-1_2
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11592-4
Online ISBN: 978-3-319-11593-1
eBook Packages: Computer ScienceComputer Science (R0)