{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,4,4]],"date-time":"2025-04-04T21:44:00Z","timestamp":1743803040800},"publisher-location":"Berlin, Heidelberg","reference-count":29,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540709039"},{"type":"electronic","value":"9783540709046"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"DOI":"10.1007\/978-3-540-70904-6_26","type":"book-chapter","created":{"date-parts":[[2007,5,17]],"date-time":"2007-05-17T11:44:43Z","timestamp":1179402283000},"page":"258-269","source":"Crossref","is-referenced-by-count":25,"title":["Path Simplification for Metro Map Layout"],"prefix":"10.1007","author":[{"given":"Damian","family":"Merrick","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Joachim","family":"Gudmundsson","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"crossref","unstructured":"Alt, H., Godau, M.: Measuring the resemblance of polygonal curves. In: Proc. 8th Annual Symposium on Computational Geometry, pp. 102\u2013109 (1992)","DOI":"10.1145\/142675.142699"},{"issue":"2","key":"26_CR2","doi-asserted-by":"publisher","first-page":"273","DOI":"10.1007\/PL00009500","volume":"23","author":"P.K. Agarwal","year":"2000","unstructured":"Agarwal, P.K., Varadarajan, K.R.: Efficient Algorithms for Approximating Polygonal Chains. Discrete & Computational Geometry\u00a023(2), 273\u2013291 (2000)","journal-title":"Discrete & Computational Geometry"},{"key":"26_CR3","doi-asserted-by":"crossref","unstructured":"Bose, J., Cheong, O., Cabello, S., Gudmundsson, J., van Kreveld, M., Speckmann, B.: Area-preserving approximations of polygonal paths. J. Discrete Alg. (2006)","DOI":"10.1016\/j.jda.2005.06.008"},{"issue":"2","key":"26_CR4","doi-asserted-by":"publisher","first-page":"150","DOI":"10.1007\/s00453-001-0096-5","volume":"33","author":"G. Barequet","year":"2002","unstructured":"Barequet, G., Chen, D.Z., Daescu, O., Goodrich, M.T., Snoeyink, J.: Efficiently approximating polygonal paths in three and higher dimensions. Algorithmica\u00a033(2), 150\u2013167 (2002)","journal-title":"Algorithmica"},{"key":"26_CR5","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/j.comgeo.2004.11.002","volume":"30","author":"S. Cabello","year":"2005","unstructured":"Cabello, S., de Berg, M., van Kreveld, M.: Schematization of networks. Computational Geometry and Applications\u00a030, 223\u2013238 (2005)","journal-title":"Computational Geometry and Applications"},{"key":"26_CR6","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1142\/S0218195996000058","volume":"6","author":"W.S. Chan","year":"1996","unstructured":"Chan, W.S., Chin, F.: Approximation of polygonal curves with minimum number of line segments or minimum error. IJCGA\u00a06, 59\u201377 (1996)","journal-title":"IJCGA"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1142\/S0218195903001086","volume":"13","author":"D.Z. Chen","year":"2003","unstructured":"Chen, D.Z., Daescu, O.: Space-efficient algorithms for approximating polygonal curves in two-dimensional space. IJCGA\u00a013, 95\u2013111 (2003)","journal-title":"IJCGA"},{"issue":"3","key":"26_CR8","first-page":"173","volume":"32","author":"D.Z. Chen","year":"2005","unstructured":"Chen, D.Z., Daescu, O., Hershberger, J., Kogge, P.M., Mi, N., Snoeyink, J.: Polygonal path simplification with angle constraints. CGTA\u00a032(3), 173\u2013187 (2005)","journal-title":"CGTA"},{"key":"26_CR9","unstructured":"CityRail network map. Web page: http:\/\/www.cityrail.info\/networkmaps\/mainmap.jsp (Accessed 6th Sept 2006)"},{"issue":"2","key":"26_CR10","doi-asserted-by":"crossref","first-page":"112","DOI":"10.3138\/FM57-6770-U75U-7727","volume":"10","author":"D. Douglas","year":"1973","unstructured":"Douglas, D., Peucker, T.: Algorithms for the reduction of the number of points required to represent a digitized line or its caricature. The Canadian Cartographer\u00a010(2), 112\u2013122 (1973)","journal-title":"The Canadian Cartographer"},{"issue":"3","key":"26_CR11","first-page":"231","volume":"56","author":"D. Eu","year":"1994","unstructured":"Eu, D., Toussaint, G.T.: On Approximating Polygonal Curves in Two and Three Dimensions. CVGIP: Graphical Model and Image Processing\u00a056(3), 231\u2013246 (1994)","journal-title":"CVGIP: Graphical Model and Image Processing"},{"key":"26_CR12","unstructured":"Friedrich, C.: jjGraph. Personal communication"},{"key":"26_CR13","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/BF02570717","volume":"14","author":"M.T. Goodrich","year":"1995","unstructured":"Goodrich, M.T.: Efficient piecewise-linear function approximation using the uniform metric. Discrete & Computational Geometry\u00a014, 445\u2013462 (1995)","journal-title":"Discrete & Computational Geometry"},{"key":"26_CR14","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., van Kreveld, M., Merrick, D.: Schematisation of Tree Drawings. Submitted to Graph Drawing (June 2006)","DOI":"10.1007\/978-3-540-70904-6_8"},{"key":"26_CR15","doi-asserted-by":"crossref","unstructured":"Gudmundsson, J., Narasimhan, G., Smid, M.H.M.: Distance-Preserving Approximations of Polygonal Paths. To appear in CGTA (2006)","DOI":"10.1016\/j.comgeo.2006.05.002"},{"issue":"4","key":"26_CR16","doi-asserted-by":"publisher","first-page":"383","DOI":"10.1142\/S0218195993000257","volume":"3","author":"L.J. Guibas","year":"1993","unstructured":"Guibas, L.J., Hershberger, J., Mitchell, J.S.B., Snoeyink, J.: Approximating Polygons and Subdivisions with Minimum Link Paths. IJCGA\u00a03(4), 383\u2013415 (1993)","journal-title":"IJCGA"},{"issue":"3-4","key":"26_CR17","first-page":"175","volume":"11","author":"J. Hershberger","year":"1998","unstructured":"Hershberger, J., Snoeyink, J.: Cartographic line simplification and polygon CSG formul\u00e6 in O(n log* n) time. Theory & Applications\u00a011(3-4), 175\u2013185 (1998)","journal-title":"Theory & Applications"},{"key":"26_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"482","DOI":"10.1007\/978-3-540-31843-9_50","volume-title":"Graph Drawing","author":"S.-H. Hong","year":"2005","unstructured":"Hong, S.-H., Merrick, D., do Nascimento, H.A.D.: The metro map layout problem. In: Pach, J. (ed.) GD 2004. LNCS, vol.\u00a03383, pp. 482\u2013491. Springer, Heidelberg (2005)"},{"key":"26_CR19","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1016\/S0734-189X(86)80027-5","volume":"36","author":"H. Imai","year":"1986","unstructured":"Imai, H., Iri, M.: Computational-geometric methods for polygonal approximations of a curve. Comp. Vision, Graphics and Image Processing\u00a036, 31\u201341 (1986)","journal-title":"Comp. Vision, Graphics and Image Processing"},{"issue":"3","key":"26_CR20","first-page":"159","volume":"9","author":"H. Imai","year":"1986","unstructured":"Imai, H., Iri, M.: An optimal algorithm for approximating a piecewise linear function. Journal of Information Processing\u00a09(3), 159\u2013162 (1986)","journal-title":"Journal of Information Processing"},{"key":"26_CR21","volume-title":"Computational Morphology","author":"H. Imai","year":"1988","unstructured":"Imai, H., Iri, M.: Polygonal approximations of a curve-formulations and algorithms. In: Toussaint, G.T. (ed.) Computational Morphology, North-Holland, Amsterdam (1988)"},{"key":"26_CR22","unstructured":"London Underground network map. Web page: http:\/\/www.tfl.gov.uk\/tube\/maps\/ (Accessed 6th Sept 2006)"},{"key":"26_CR23","volume-title":"Computational Morphology","author":"A. Melkman","year":"1988","unstructured":"Melkman, A., O\u2019Rourke, J.: On polygonal chain approximation. In: Toussaint, G.T. (ed.) Computational Morphology, North-Holland, Amsterdam (1988)"},{"key":"26_CR24","unstructured":"Merrick, D., Gudmundsson, J.: Increasing the readability of graph drawings with centrality-based scaling. In: Proc. APVIS 2006, pp. 67\u201376 (2006)"},{"key":"26_CR25","unstructured":"Merrick, D., Gudmundsson, J.: $\\mathcal C$ -Directed Path Simplification for Metro Map Layout. http:\/\/www.dmist.net\/metromap.pdf (Accessed 6th Sept 2006)"},{"key":"26_CR26","doi-asserted-by":"crossref","unstructured":"Neyer, G.: Line simplification with restricted orientations. In: Proc. 6th International Workshop on Algorithms and Data Structures, pp. 13\u201324 (1999)","DOI":"10.1007\/3-540-48447-7_2"},{"key":"26_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","DOI":"10.1007\/11618058_29","volume-title":"Graph Drawing","author":"M. N\u00f6llenburg","year":"2006","unstructured":"N\u00f6llenburg, M., Wolff, A.: A mixed-integer program for drawing high-quality metro maps. In: Healy, P., Nikolov, N.S. (eds.) GD 2005. LNCS, vol.\u00a03843, Springer, Heidelberg (2006)"},{"key":"26_CR28","doi-asserted-by":"crossref","unstructured":"Stott, J., Rodgers, P.: Metro map layout using multicriteria optimization. In: Proc. 8th Interational Conference on Information Visualisation, pp. 355\u2013362 (2004)","DOI":"10.1109\/IV.2004.1320168"},{"key":"26_CR29","unstructured":"Toussaint, G.T.: On the Complexity of Approximating Polygonal Curves in the Plane. In: Proc. of the International Symposium on Robotics and Automation (IASTED), pp. 311\u2013318 (1985)"}],"container-title":["Lecture Notes in Computer Science","Graph Drawing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-540-70904-6_26.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,19]],"date-time":"2020-11-19T00:11:30Z","timestamp":1605744690000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-540-70904-6_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[null]]},"ISBN":["9783540709039","9783540709046"],"references-count":29,"URL":"https:\/\/doi.org\/10.1007\/978-3-540-70904-6_26","relation":{},"subject":[]}}