{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,30]],"date-time":"2026-09-30T08:48:43Z","timestamp":1790758123587,"version":"4.1.0"},"reference-count":15,"publisher":"Springer Science and Business Media LLC","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,10]]},"DOI":"10.1007\/s00224-009-9184-8","type":"journal-article","created":{"date-parts":[[2009,2,4]],"date-time":"2009-02-04T18:49:24Z","timestamp":1233773364000},"page":"613-636","source":"Crossref","is-referenced-by-count":8,"title":["Trimming of Graphs, with Application to Point Labeling"],"prefix":"10.1007","volume":"47","author":[{"given":"Thomas","family":"Erlebach","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Torben","family":"Hagerup","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Moritz","family":"Minzlaff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2009,2,5]]},"reference":[{"key":"9184_CR1","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1016\/S0925-7721(98)00028-5","volume":"11","author":"P.K. Agarwal","year":"1998","unstructured":"Agarwal, P.K., van Kreveld, M., Suri, S.: Label placement by maximum independent set in rectangles. Comput. Geom. Theory Appl. 11, 209\u2013218 (1998)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9184_CR2","doi-asserted-by":"crossref","first-page":"153","DOI":"10.1145\/174644.174650","volume":"41","author":"B.S. Baker","year":"1994","unstructured":"Baker, B.S.: Approximation algorithms for NP-complete problems on planar graphs. J. ACM 41, 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"1\u20132","key":"9184_CR3","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1016\/S0304-3975(97)00228-4","volume":"209","author":"H.L. Bodlaender","year":"1998","unstructured":"Bodlaender, H.L.: A partial k-arboretum of graphs with bounded treewidth. Theor. Comput. Sci. 209(1\u20132), 1\u201345 (1998)","journal-title":"Theor. Comput. Sci."},{"issue":"4","key":"9184_CR4","first-page":"141","volume":"3","author":"H.L. Bodlaender","year":"1999","unstructured":"Bodlaender, H.L.: A note on domino treewidth. Discrete Math. Theor. Comput. Sci. 3(4), 141\u2013150 (1999)","journal-title":"Discrete Math. Theor. Comput. Sci."},{"key":"9184_CR5","doi-asserted-by":"crossref","first-page":"481","DOI":"10.1002\/jgt.3190200412","volume":"20","author":"G. Ding","year":"1995","unstructured":"Ding, G., Oporowski, B.: Some results on tree decomposition of graphs. J. Graph Theory 20, 481\u2013499 (1995)","journal-title":"J. Graph Theory"},{"issue":"1","key":"9184_CR6","doi-asserted-by":"crossref","first-page":"75","DOI":"10.1016\/S0304-3975(02)00433-4","volume":"296","author":"R. Duncan","year":"2003","unstructured":"Duncan, R., Qian, J., Vigneron, A., Zhu, B.: Polynomial time algorithms for three-label point labeling. Theor. Comput. Sci. 296(1), 75\u201387 (2003)","journal-title":"Theor. Comput. Sci."},{"issue":"3","key":"9184_CR7","doi-asserted-by":"crossref","first-page":"477","DOI":"10.1137\/0134037","volume":"34","author":"M.R. Garey","year":"1978","unstructured":"Garey, M.R., Graham, R.L., Johnson, D.S., Knuth, D.E.: Complexity results for bandwidth minimization. SIAM J. Appl. Math. 34(3), 477\u2013495 (1978)","journal-title":"SIAM J. Appl. Math."},{"key":"9184_CR8","doi-asserted-by":"crossref","first-page":"130","DOI":"10.1145\/2455.214106","volume":"32","author":"D.S. Hochbaum","year":"1985","unstructured":"Hochbaum, D.S., Maass, W.: Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM 32, 130\u2013136 (1985)","journal-title":"J. ACM"},{"key":"9184_CR9","doi-asserted-by":"crossref","first-page":"127","DOI":"10.1007\/BF02187876","volume":"2","author":"D. Haussler","year":"1987","unstructured":"Haussler, D., Welzl, E.: \u03b5-nets and simplex range queries. Discrete Comput. Geom. 2, 127\u2013151 (1987)","journal-title":"Discrete Comput. Geom."},{"issue":"4","key":"9184_CR10","doi-asserted-by":"crossref","first-page":"125","DOI":"10.1016\/j.ipl.2006.04.006","volume":"99","author":"M. Jiang","year":"2006","unstructured":"Jiang, M.: A new approximation algorithm for labeling points with circle pairs. Inf. Process. Lett. 99(4), 125\u2013129 (2006)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9184_CR11","doi-asserted-by":"crossref","first-page":"341","DOI":"10.1007\/s00453-003-1063-0","volume":"38","author":"S.-H. Poon","year":"2003","unstructured":"Poon, S.-H., Shin, C.-S., Strijk, T., Uno, T., Wolff, A.: Labeling points with weights. Algorithmica 38(2), 341\u2013362 (2003)","journal-title":"Algorithmica"},{"key":"9184_CR12","series-title":"Lecture Notes Comput. Sci.","doi-asserted-by":"crossref","first-page":"368","DOI":"10.1007\/3-540-45253-2_34","volume-title":"Proc. 8th Annual European Symposium on Algorithms (ESA\u201900)","author":"Z. Qin","year":"2000","unstructured":"Qin, Z., Wolff, A., Xu, Y., Zhu, B.: New algorithms for two-label point labeling. In: Paterson, M. (ed.) Proc. 8th Annual European Symposium on Algorithms (ESA\u201900). Lecture Notes Comput. Sci., vol. 1879, pp. 368\u2013379. Springer, Berlin (2000)"},{"issue":"3","key":"9184_CR13","doi-asserted-by":"crossref","first-page":"309","DOI":"10.1016\/0196-6774(86)90023-4","volume":"7","author":"N. Robertson","year":"1986","unstructured":"Robertson, N., Seymour, P.D.: Graph minors. II. Algorithmic aspects of tree-width. J. Algorithms 7(3), 309\u2013322 (1986)","journal-title":"J. Algorithms"},{"key":"9184_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":"van Kreveld, M., Strijk, T., Wolff, A.: Point labeling with sliding labels. Comput. Geom. Theory Appl. 13, 21\u201347 (1999)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9184_CR15","unstructured":"Wolff, A., Strijk, T.: The map-labeling bibliography. (1996\u20132008). http:\/\/i11www.ira.uka.de\/map-labeling\/bibliography"}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-009-9184-8.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,4,7]],"date-time":"2019-04-07T07:09:20Z","timestamp":1554620960000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-009-9184-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,2,5]]},"references-count":15,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2010,10]]}},"alternative-id":["9184"],"URL":"https:\/\/doi.org\/10.1007\/s00224-009-9184-8","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,2,5]]}}}