{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,5]],"date-time":"2024-09-05T14:01:23Z","timestamp":1725544883255},"publisher-location":"Berlin, Heidelberg","reference-count":28,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540424949"},{"type":"electronic","value":"9783540446798"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44679-6_21","type":"book-chapter","created":{"date-parts":[[2010,2,9]],"date-time":"2010-02-09T12:00:37Z","timestamp":1265716837000},"page":"191-200","source":"Crossref","is-referenced-by-count":1,"title":["Polynomial Time Algorithms for Three-Label Point Labeling"],"prefix":"10.1007","author":[{"given":"Rob","family":"Duncan","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jianbo","family":"Qian","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Binhai","family":"Zhu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,7,31]]},"reference":[{"key":"21_CR1","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"P. Agarwal","year":"1998","unstructured":"P. Agarwal, M. van Kreveld and S. Suri Label placement by maximum independent set in rectangles. Comp. Geom. Theory and Appl., 11:209\u2013218, 1998.","journal-title":"Comp. Geom. Theory and Appl"},{"key":"21_CR2","first-page":"75","volume":"1","author":"J. Christensen","year":"1993","unstructured":"J. Christensen, J. Marks, and S. Shieber Algorithms for cartographic label placement. In Proc. 1993 ASPRS\/ACSM Annual Convention and Exposition, volume 1, pages 75\u201389, 1993.","journal-title":"Proc. 1993 ASPRS\/ACSM Annual Convention and Exposition"},{"key":"21_CR3","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1145\/212332.212334","volume":"14","author":"J. Christenson","year":"1995","unstructured":"J. Christenson, J. Marks, and S. Shieber An Empirical Study of Algorithms for Point-Feature Label Placement, ACM Transactions on Graphics,14:203\u2013222, 1995.","journal-title":"ACM Transactions on Graphics"},{"key":"21_CR4","doi-asserted-by":"crossref","first-page":"68","DOI":"10.1145\/129617.129620","volume":"35","author":"J. Doerschler","year":"1992","unstructured":"J. Doerschler and H. Freeman A rule-based system for cartographic name placement. CACM, 35:68\u201379, 1992.","journal-title":"CACM"},{"key":"21_CR5","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"265","DOI":"10.1007\/3-540-57155-8_254","volume-title":"Proc. 3rd Worksh. Algorithms and Data Structures","author":"A. Datta","year":"1993","unstructured":"A. Datta, II.-P. Lenhof, C. Schwarz, and M. Smid Static and dynamic algorithms for k-point clustering problems, In Proc. 3rd Worksh. Algorithms and Data Structures, springer-verlag, LNCS 709, pages 265\u2013276, 1993."},{"key":"21_CR6","doi-asserted-by":"crossref","unstructured":"S. Doddi, M. Marathe and B. Moret Point set labeling with specified positions. In Proc. 16th Annu. ACM Sympos. Comput. Geom., pages 182\u2013190, June, 2000.","DOI":"10.1145\/336154.336200"},{"key":"21_CR7","unstructured":"S. Doddi, M. Marathe, A. Mirzaian, B. Moret and B. Zhu Map labeling and its generalizations. In Proc. 8th ACM-SIAM Symp on Discrete Algorithms (SODA\u201997), New Orleans, LA, pages 148\u2013157, Jan, 1997."},{"key":"21_CR8","doi-asserted-by":"crossref","unstructured":"M. Formann and F. Wagner A packing problem with applications to lettering of maps. In Proc. 7th Annu. ACM Sympos. Comput. Geom., pages 281\u2013288, 1991.","DOI":"10.1145\/109648.109680"},{"key":"21_CR9","volume-title":"Computers and Intractability: A Guide to the Theory of NP-completeness","author":"M. Garey","year":"1979","unstructured":"M. Garey and D. Johnson Computers and Intractability: A Guide to the Theory of NP-completeness. Freeman, San Francisco, CA, 1979."},{"key":"21_CR10","doi-asserted-by":"publisher","first-page":"128","DOI":"10.1559\/152304075784313304","volume":"2","author":"E. Imhof","year":"1975","unstructured":"E. Imhof Positioning names on maps. The American Cartographer, 2:128\u2013144, 1975.","journal-title":"The American Cartographer"},{"key":"21_CR11","doi-asserted-by":"crossref","unstructured":"C. Iturriaga and A. Lubiw Elastic labels: the two-axis case. In Proc. Graph Drawing\u201997, pages 181\u2013192, 1997.","DOI":"10.1007\/3-540-63938-1_61"},{"key":"21_CR12","doi-asserted-by":"publisher","first-page":"36","DOI":"10.1109\/38.35536","volume":"5","author":"C. Jones","year":"1989","unstructured":"C. Jones Cartographic name placement with Prolog. Proc. IEEE Computer Graphics and Applications, 5:36\u201347, 1989.","journal-title":"Proc. IEEE Computer Graphics and Applications"},{"key":"21_CR13","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"D. Knuth","year":"1992","unstructured":"D. Knuth and A. Raghunathan The problem of compatible representatives. SIAM J. Disc. Math., 5:422\u2013427, 1992.","journal-title":"SIAM J. Disc. Math"},{"key":"21_CR14","doi-asserted-by":"crossref","first-page":"21","DOI":"10.1016\/S0925-7721(99)00005-X","volume":"13","author":"M. Kreveld van","year":"1999","unstructured":"M. van Kreveld, T. Strijk and A. Wolff Point set labeling with sliding labels. Comp. Geom. Theory and Appl., 13:21\u201347, 1999.","journal-title":"Comp. Geom. Theory and Appl"},{"key":"21_CR15","doi-asserted-by":"crossref","unstructured":"K. Kakoulis and I. Tollis An algorithm for labeling edges of hierarchical drawings. In Proc. Graph Drawing\u201997, pages 169\u2013180, 1997.","DOI":"10.1007\/3-540-63938-1_60"},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"K. Kakoulis and I. Tollis A unified approach to labeling graphical features. Proc. 14th Annu. ACM Sympos. Comput. Geom., pages 347\u2013356, 1998.","DOI":"10.1145\/276884.276923"},{"key":"21_CR17","unstructured":"K. Kakoulis and I. Tollis On the multiple label placement problem. In Proc. 10th Canadian Conf. on Comput. Geom., pages 66\u201367, 1998."},{"key":"21_CR18","doi-asserted-by":"crossref","unstructured":"F.P. Preparata and M.I. Shamos Computational Geometry: An Introduction. Springer-Verlag, 1985.","DOI":"10.1007\/978-1-4612-1098-6"},{"issue":"4","key":"21_CR19","doi-asserted-by":"publisher","first-page":"201","DOI":"10.1016\/S0020-0190(98)00002-7","volume":"65","author":"C.K. Poon","year":"1998","unstructured":"C.K. Poon, B. Zhu and F. Chin, A polynomial time solution for labeling a rectilinear map. Inform. Process. Lett., 65(4):201\u2013207, Feb, 1998.","journal-title":"Inform. Process. Lett"},{"key":"21_CR20","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/3-540-45253-2_34","volume-title":"Proc. 8th European Symp. on Algorithms (ESA\u201900)","author":"Z.P. Qin","year":"2000","unstructured":"Z.P. Qin, A. Wolff, Y. Xu and B. Zhu, New algorithms for two-label point labeling. Proc. 8th European Symp. on Algorithms (ESA\u201900), pages 368\u2013379, Springer-Verlag, LNCS series 1879, 2000."},{"key":"21_CR21","unstructured":"M. Spriggs On the complexity of labeling maps with square pairs. manuscript, 2000."},{"key":"21_CR22","unstructured":"M. Spriggs and M. Keil A new bound for map labeling with uniform circle pairs. Inform. Process. Lett., submitted, 2000."},{"key":"21_CR23","unstructured":"T. Strijk and A. Wolff Labeling points with circles. Tech Report B 99-08, Institut fur Informatik, Freie Universitat, Berlin, April, 1999."},{"key":"21_CR24","doi-asserted-by":"publisher","first-page":"161","DOI":"10.1016\/0020-0190(94)90001-9","volume":"52","author":"F. Wagner","year":"1994","unstructured":"F. Wagner Approximate map labeling is in O(n log n). Inform. Process. Lett., 52:161\u2013165, 1994.","journal-title":"Inform. Process. Lett"},{"key":"21_CR25","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1007\/3-540-40996-3_36","volume-title":"Proc. 11th Intl Symp. on Algorithms and Computation (ISAAC\u201900)","author":"A. Wolff","year":"2000","unstructured":"A. Wolff, M. Thon and Y. Xu \u201cA better lower bound for two-circle point labelinga,\u201d In Proc. 11th Intl Symp. on Algorithms and Computation (ISAAC\u201900), pages 422\u2013431, Springer-Verlag, LNCS series 1969, 2000."},{"key":"21_CR26","doi-asserted-by":"crossref","unstructured":"F. Wagner and A. Wolff Map labeling heuristics: Provably good and practically useful. In Proc. 11th Annu. ACM Sympos. Comput. Geom., pages 109\u2013118, 1995.","DOI":"10.1145\/220279.220291"},{"key":"21_CR27","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/3-540-46632-0_15","volume-title":"Proc. 10th Intl Symp. on Algorithms and Computation (ISAAC\u201999)","author":"B. Zhu","year":"1999","unstructured":"B. Zhu and C.K. Poon \u201cEfficient approximation algorithms for multi-label map labeling,\u201d In Proc. 10th Intl Symp. on Algorithms and Computation (ISAAC\u201999), pages 143\u2013152, Springer-Verlag, LNCS series 1741, 1999."},{"key":"21_CR28","doi-asserted-by":"crossref","unstructured":"B. Zhu and Z.P. Qin New approximation algorithms for map labeling with sliding labels. J. of Combinatorial Optimization, accepted, 2000.","DOI":"10.1023\/A:1009859026994"}],"container-title":["Lecture Notes in Computer Science","Computing and Combinatorics"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44679-6_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,25]],"date-time":"2019-05-25T17:32:55Z","timestamp":1558805575000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44679-6_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540424949","9783540446798"],"references-count":28,"URL":"https:\/\/doi.org\/10.1007\/3-540-44679-6_21","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]}}}