{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,10]],"date-time":"2026-04-10T10:02:32Z","timestamp":1775815352625,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540357537","type":"print"},{"value":"9783540357551","type":"electronic"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2006]]},"DOI":"10.1007\/11785293_30","type":"book-chapter","created":{"date-parts":[[2006,6,26]],"date-time":"2006-06-26T05:24:10Z","timestamp":1151299450000},"page":"316-327","source":"Crossref","is-referenced-by-count":16,"title":["Better Approximation Schemes for Disk Graphs"],"prefix":"10.1007","author":[{"given":"Erik Jan","family":"van Leeuwen","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"30_CR1","first-page":"516","volume-title":"SODA 2004","author":"P.K. Agarwal","year":"2004","unstructured":"Agarwal, P.K., Overmars, M., Sharir, M.: Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks. In: SODA 2004, pp. 516\u2013525. SIAM, Philadelphia (2004)"},{"issue":"2","key":"30_CR2","doi-asserted-by":"publisher","first-page":"134","DOI":"10.1016\/j.jalgor.2003.10.001","volume":"52","author":"J. Alber","year":"2003","unstructured":"Alber, J., Fiala, J.: Geometric Separation and Exact Solutions for the Parameterized Independent Set Problem on Disk Graphs. J. Algorithms\u00a052(2), 134\u2013151 (2003)","journal-title":"J. Algorithms"},{"issue":"1","key":"30_CR3","doi-asserted-by":"publisher","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\u00a041(1), 153\u2013180 (1994)","journal-title":"J. ACM"},{"issue":"2","key":"30_CR4","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"T.M. Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time Approximation Schemes for Packing and Piercing Fat Objects. J. Algorithms\u00a046(2), 178\u2013189 (2003)","journal-title":"J. Algorithms"},{"issue":"1","key":"30_CR5","doi-asserted-by":"publisher","first-page":"19","DOI":"10.1016\/j.ipl.2003.09.019","volume":"89","author":"T.M. Chan","year":"2004","unstructured":"Chan, T.M.: A Note on Maximum Independent Sets in Rectangle Intersection Graphs. Inf. Proc. Let.\u00a089(1), 19\u201323 (2004)","journal-title":"Inf. Proc. Let."},{"issue":"1\u20133","key":"30_CR6","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1016\/0012-365X(90)90358-O","volume":"86","author":"B.N. Clark","year":"1990","unstructured":"Clark, B.N., Colbourn, C.J., Johnson, D.S.: Unit Disk Graphs. Discr. Math.\u00a086(1\u20133), 165\u2013177 (1990)","journal-title":"Discr. Math."},{"issue":"4","key":"30_CR7","doi-asserted-by":"crossref","first-page":"309","DOI":"10.3233\/FI-1995-2241","volume":"22","author":"D. Eppstein","year":"1995","unstructured":"Eppstein, D., Miller, G.L., Teng, S.-H.: A Deterministic Linear Time Algorithm for Geometric Separators and its Applications. Fund. Inform.\u00a022(4), 309\u2013329 (1995)","journal-title":"Fund. Inform."},{"issue":"6","key":"30_CR8","doi-asserted-by":"publisher","first-page":"1302","DOI":"10.1137\/S0097539702402676","volume":"34","author":"T. Erlebach","year":"2005","unstructured":"Erlebach, T., Jansen, K., Seidel, E.: Polynomial-time Approximation Schemes for Geometric Intersection Graphs. SIAM J. Computing\u00a034(6), 1302\u20131323 (2005)","journal-title":"SIAM J. Computing"},{"issue":"1","key":"30_CR9","doi-asserted-by":"publisher","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\u00a032(1), 130\u2013136 (1985)","journal-title":"J. ACM"},{"issue":"2","key":"30_CR10","doi-asserted-by":"publisher","first-page":"238","DOI":"10.1006\/jagm.1997.0903","volume":"26","author":"D.B. Hunt III","year":"1998","unstructured":"Hunt III, D.B., Marathe, M.V., Radhakrishnan, V., Ravi, S.S., Rosenkrantz, D.J., Stearns, R.E.: NC-Approximation Schemes for NP- and PSPACE-Hard Problems for Geometric Graphs. J. Algorithms\u00a026(2), 238\u2013274 (1998)","journal-title":"J. Algorithms"},{"key":"30_CR11","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Ver. S\u00e4chs. Ak. Wiss. Leipzig, Math.-Phys. Kl.\u00a088, 141\u2013164 (1936)"},{"key":"30_CR12","unstructured":"Malesi\u0144ska, E.: Graph-Theoretical Models for Frequency Assignment Problems, PhD Thesis, Technical University of Berlin, Berlin (1997)"},{"key":"30_CR13","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1002\/net.3230250205","volume":"25","author":"M.V. Marathe","year":"1995","unstructured":"Marathe, M.V., Breu, H., Hunt III, H.B., Ravi, S.S., Rosenkrantz, D.J.: Simple Heuristics for Unit Disk Graphs. Networks\u00a025, 59\u201368 (1995)","journal-title":"Networks"},{"key":"30_CR14","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"448","DOI":"10.1007\/11561071_41","volume-title":"Algorithms \u2013 ESA 2005","author":"D. Marx","year":"2005","unstructured":"Marx, D.: Efficient Approximation Schemes for Geometric Problems? In: Brodal, G.S., Leonardi, S. (eds.) ESA 2005. LNCS, vol.\u00a03669, pp. 448\u2013459. Springer, Heidelberg (2005)"},{"key":"30_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"194","DOI":"10.1007\/978-3-540-46515-7_16","volume-title":"Discrete and Computational Geometry","author":"T. Matsui","year":"2000","unstructured":"Matsui, T.: Approximation Algorithms for Maximum Independent Set Problems and Fractional Coloring Problems on Unit Disk Graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol.\u00a01763, pp. 194\u2013200. Springer, Heidelberg (2000)"},{"issue":"1","key":"30_CR16","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"G.L. Miller","year":"1997","unstructured":"Miller, G.L., Teng, S.-H., Thurston, W., Vavasis, S.A.: Separators for Sphere-Packings and Nearest Neighbor Graphs. J. ACM\u00a044(1), 1\u201329 (1997)","journal-title":"J. ACM"},{"key":"30_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"214","DOI":"10.1007\/978-3-540-30559-0_18","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"T. Nieberg","year":"2004","unstructured":"Nieberg, T., Hurink, J.L., Kern, W.: A Robust PTAS for Maximum Weight Independent Sets in Unit Disk Graphs. In: Hromkovi\u010d, J., Nagl, M., Westfechtel, B. (eds.) WG 2004. LNCS, vol.\u00a03353, pp. 214\u2013221. Springer, Heidelberg (2004)"},{"key":"30_CR18","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/0095-8956(83)90079-5","volume":"35","author":"N. Robertson","year":"1983","unstructured":"Robertson, N., Seymour, P.D.: Graph Minors. I. Excluding a Forest. J. Comb. Th. B\u00a035, 39\u201361 (1983)","journal-title":"J. Comb. Th. B"},{"issue":"4","key":"30_CR19","doi-asserted-by":"publisher","first-page":"529","DOI":"10.1137\/S0895480194275825","volume":"10","author":"J.A. Telle","year":"1997","unstructured":"Telle, J.A., Proskurowski, A.: Algorithms for Vertex Partitioning Problems on Partial k-Trees. SIAM J. Disc. Math.\u00a010(4), 529\u2013550 (1997)","journal-title":"SIAM J. Disc. Math."},{"key":"30_CR20","unstructured":"van Leeuwen, E.J.: Optimization Problems on Mobile Ad Hoc Networks \u2013 Algorithms for Disk Graphs, Master\u2019s Thesis INF\/SCR-04-32, Inst. of Information and Computing Sciences, Utrecht Univ. (2004)"},{"key":"30_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1007\/11604686_31","volume-title":"Graph-Theoretic Concepts in Computer Science","author":"E.J. Leeuwen van","year":"2005","unstructured":"van Leeuwen, E.J.: Approximation Algorithms for Unit Disk Graphs. In: Kratsch, D. (ed.) WG 2005. LNCS, vol.\u00a03787, pp. 351\u2013361. Springer, Heidelberg (2005)"}],"container-title":["Lecture Notes in Computer Science","Algorithm Theory \u2013 SWAT 2006"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/11785293_30","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,15]],"date-time":"2020-04-15T20:07:57Z","timestamp":1586981277000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/11785293_30"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2006]]},"ISBN":["9783540357537","9783540357551"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/11785293_30","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2006]]}}}