{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,31]],"date-time":"2025-07-31T00:39:39Z","timestamp":1753922379739,"version":"3.37.3"},"reference-count":16,"publisher":"Springer Science and Business Media LLC","issue":"7","license":[{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T00:00:00Z","timestamp":1580515200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2020,7]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A road map can be interpreted as a graph embedded in the plane, in which each vertex corresponds to a road junction and each edge to a particular road section. In this paper, we consider the computational cartographic problem to place non-overlapping road labels along the edges so that as many road sections as possible are identified by their name, i.e., covered by a label. We show that this is -hard in general, but the problem can be solved in <jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^3)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>O<\/mml:mi><mml:mo>(<\/mml:mo><mml:msup><mml:mi>n<\/mml:mi><mml:mn>3<\/mml:mn><\/mml:msup><mml:mo>)<\/mml:mo><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> time if the road map is an embedded tree with <jats:italic>n<\/jats:italic> vertices and constant maximum degree. This special case is not only of theoretical interest, but our algorithm in fact provides a very useful subroutine in exact or heuristic algorithms for labeling general road maps.<\/jats:p>","DOI":"10.1007\/s00453-020-00678-7","type":"journal-article","created":{"date-parts":[[2020,2,1]],"date-time":"2020-02-01T05:02:56Z","timestamp":1580533376000},"page":"1881-1908","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Placing Labels in Road Maps: Algorithms and Complexity"],"prefix":"10.1007","volume":"82","author":[{"given":"Andreas","family":"Gemsa","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6638-7250","authenticated-orcid":false,"given":"Benjamin","family":"Niedermann","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-0454-3937","authenticated-orcid":false,"given":"Martin","family":"N\u00f6llenburg","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,2,1]]},"reference":[{"issue":"2","key":"678_CR1","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1559\/152304000783547902","volume":"27","author":"F Chiri\u00e9","year":"2000","unstructured":"Chiri\u00e9, F.: Automated name placement with high cartographic quality: city street maps. Cartogr. Geogr. Inf. Sci. 27(2), 101\u2013110 (2000)","journal-title":"Cartogr. Geogr. Inf. Sci."},{"issue":"4","key":"678_CR2","doi-asserted-by":"publisher","first-page":"13","DOI":"10.3138\/U3N2-6363-130N-H870","volume":"33","author":"S Edmondson","year":"1996","unstructured":"Edmondson, S., Christensen, J., Marks, J., Shieber, S.M.: A general cartographic labelling algorithm. Cartographica 33(4), 13\u201324 (1996)","journal-title":"Cartographica"},{"issue":"2","key":"678_CR3","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1559\/152304075784313304","volume":"2","author":"E Imhof","year":"1975","unstructured":"Imhof, E.: Positioning names on maps. Am. Cartogr. 2(2), 128\u2013144 (1975)","journal-title":"Am. Cartogr."},{"issue":"2","key":"678_CR4","doi-asserted-by":"publisher","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"678_CR5","doi-asserted-by":"crossref","unstructured":"Maass, S., D\u00f6llner, J.: Embedded labels for line features in interactive 3d virtual environments. In: Computer Graphics, Virtual Reality, Visualisation and Interaction (AFRIGRAPH\u201907), pp. 53\u201359. ACM Press (2007)","DOI":"10.1145\/1294685.1294695"},{"key":"678_CR6","doi-asserted-by":"crossref","unstructured":"Niedermann, B., N\u00f6llenburg, M.: An algorithmic framework for labeling road maps. In: Geographic Information Science (GIScience\u201916), Volume 9927 of Lecture Notes in Computer Science, pp. 308\u2013322. Springer (2016)","DOI":"10.1007\/978-3-319-45738-3_20"},{"key":"678_CR7","doi-asserted-by":"crossref","unstructured":"Neyer, G., Wagner, F.: Labeling downtown. In: Algorithms and Complexity (CIAC\u201900), Volume 1767 of Lecture Notes in Computer Science, pp. 113\u2013124. Springer, Berlin (2000)","DOI":"10.1007\/3-540-46521-9_10"},{"key":"678_CR8","unstructured":"Reimer, A., Rylov, M.: Point-feature lettering of high cartographic quality: a multi-criteria model with practical implementation. In: European Workshop on Computational Geometry (EuroCG\u201914) (2014)"},{"key":"678_CR9","doi-asserted-by":"crossref","unstructured":"Schwartges, N., Morgan, B., Haunert, J.-H., Wolff, A.: Labeling streets along a route in interactive 3D maps using billboards. In: AGILE 2015, Lecture Notes in Geoinformation and Cartography, pp. 269\u2013287. Springer (2015)","DOI":"10.1007\/978-3-319-16787-9_16"},{"key":"678_CR10","unstructured":"Strijk, T.: Geometric algorithms for cartographic label placement. Dissertation, Utrecht University (2001)"},{"key":"678_CR11","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1016\/S0304-3975(01)00292-4","volume":"285","author":"S Seibert","year":"2002","unstructured":"Seibert, S., Unger, W.: The hardness of placing street names in a Manhattan type map. Theor. Comput. Sci. 285, 89\u201399 (2002)","journal-title":"Theor. Comput. Sci."},{"key":"678_CR12","doi-asserted-by":"crossref","unstructured":"Schwartges, N., Wolff, A., Haunert, J.-H.: Labeling streets in interactive maps using embedded labels. In: Advances in Geographic Information Systems (ACM-GIS\u201914), pp. 517\u2013520. ACM Press (2014)","DOI":"10.1145\/2666310.2666494"},{"key":"678_CR13","first-page":"1293","volume-title":"Handbook of Discrete and Computational Geometry. Chapter 58","author":"M van Kreveld","year":"2010","unstructured":"van Kreveld, M.: Geographic information systems. In: Goodman, J.E., O\u2019Rourke, J., T\u00f3th, C.D. (eds.) Handbook of Discrete and Computational Geometry. Chapter 58, 2nd edn, pp. 1293\u20131314. Chapman and Hall\/CRC, Boca Raton, FL (2010)","edition":"2"},{"key":"678_CR14","doi-asserted-by":"crossref","unstructured":"Vaaraniemi, M., Treib, M., Westermann, R.: Temporally coherent realtime labeling of dynamic scenes. In: Computing Geospatial Research Applications (COM.Geo\u201912), pp. 17:1\u201317:10. ACM Press (2012)","DOI":"10.1145\/2345316.2345337"},{"key":"678_CR15","doi-asserted-by":"crossref","unstructured":"Wolff, A., Knipping, L., van Kreveld, M., Strijk, T., Agarwal, P.K.: A simple and efficient algorithm for high-quality line labeling. In: Innovations in GIS VII: GeoComputation. Chapter 11, pp. 147\u2013159. Taylor & Francis (2000)","DOI":"10.1201\/9781482268263-16"},{"key":"678_CR16","unstructured":"Wolff, A., Strijk, T.: The map labeling bibliography. http:\/\/liinwww.ira.uka.de\/bibliography\/Theory\/map.labeling.html (2009). Accessed 27 Jan 2020"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00678-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-020-00678-7\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-020-00678-7.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,1,31]],"date-time":"2021-01-31T00:12:01Z","timestamp":1612051921000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-020-00678-7"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,2,1]]},"references-count":16,"journal-issue":{"issue":"7","published-print":{"date-parts":[[2020,7]]}},"alternative-id":["678"],"URL":"https:\/\/doi.org\/10.1007\/s00453-020-00678-7","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"type":"print","value":"0178-4617"},{"type":"electronic","value":"1432-0541"}],"subject":[],"published":{"date-parts":[[2020,2,1]]},"assertion":[{"value":"21 June 2018","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2020","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 February 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}