{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:28:12Z","timestamp":1760441292521,"version":"3.41.0"},"publisher-location":"Berlin, Heidelberg","reference-count":41,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662483497"},{"type":"electronic","value":"9783662483503"}],"license":[{"start":{"date-parts":[[2015,1,1]],"date-time":"2015-01-01T00:00:00Z","timestamp":1420070400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2015]]},"DOI":"10.1007\/978-3-662-48350-3_60","type":"book-chapter","created":{"date-parts":[[2015,9,1]],"date-time":"2015-09-01T01:40:34Z","timestamp":1441071634000},"page":"717-728","source":"Crossref","is-referenced-by-count":14,"title":["Approximation Algorithms for Polynomial-Expansion and Low-Density Graphs"],"prefix":"10.1007","author":[{"given":"Sariel","family":"Har-Peled","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kent","family":"Quanrud","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2015,11,12]]},"reference":[{"key":"60_CR1","doi-asserted-by":"crossref","unstructured":"Adamaszek, A., Wiese, A.: Approximation schemes for maximum weight independent set of rectangles. In: Proc. 54th Annu. IEEE Sympos. Found. Comput. Sci. (FOCS), pp. 400\u2013409 (2013)","DOI":"10.1109\/FOCS.2013.50"},{"key":"60_CR2","first-page":"400","volume-title":"Proc. 25th ACM-SIAM Sympos","author":"A. Adamaszek","year":"2014","unstructured":"Adamaszek, A., Wiese, A.: A QPTAS for maximum weight independent set of polygons with polylogarithmic many vertices. In: Proc. 25th ACM-SIAM Sympos. Discrete Algs. (SODA), pp. 400\u2013409 (2014)"},{"key":"60_CR3","doi-asserted-by":"crossref","unstructured":"Agarwal, P.K., Pach, J., Sharir, M.: State of the union\u2013of geometric objects. In: Goodman, J.E., Pach, J., Pollack, R. (eds.) Surveys in Discrete and Computational Geometry Twenty Years Later. Contemporary Mathematics, vol.\u00a0453, pp. 9\u201348. Amer. Math. Soc. (2008)","DOI":"10.1090\/conm\/453\/08794"},{"key":"60_CR4","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1070\/SM1970v010n03ABEH001677","volume":"10","author":"E.M. Andreev","year":"1970","unstructured":"Andreev, E.M.: On convex polyhedra in lobachevsky spaces. Sbornik: Mathematics\u00a010, 413\u2013440 (1970)","journal-title":"Sbornik: Mathematics"},{"issue":"2","key":"60_CR5","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/120891241","volume":"43","author":"B. Aronov","year":"2014","unstructured":"Aronov, B., de Berg, M., Ezra, E., Sharir, M.: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput.\u00a043(2), 543\u2013572 (2014)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"60_CR6","doi-asserted-by":"publisher","first-page":"3248","DOI":"10.1137\/090762968","volume":"39","author":"B. Aronov","year":"2010","unstructured":"Aronov, B., Ezra, E., Sharir, M.: Small-size \u03b5-nets for axis-parallel rectangles and boxes. SIAM J. Comput.\u00a039(7), 3248\u20133282 (2010)","journal-title":"SIAM J. Comput."},{"key":"60_CR7","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. Assoc. Comput. Mach.\u00a041, 153\u2013180 (1994)","journal-title":"J. Assoc. Comput. Mach."},{"key":"60_CR8","unstructured":"Cabello, S., Gajser, D.: Simple ptas\u2019s for families of graphs excluding a minor. CoRR, abs\/1410.5778 (2014)"},{"key":"60_CR9","doi-asserted-by":"crossref","unstructured":"Chalopin, J., Gon\u00e7alves, D.: Every planar graph is the intersection graph of segments in the plane: extended abstract. In: Proc. 41st Annu. ACM Sympos. Theory Comput. (STOC), pp. 631\u2013638 (2009)","DOI":"10.1145\/1536414.1536500"},{"issue":"2","key":"60_CR10","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"},{"key":"60_CR11","unstructured":"Chan, T.M., Grant, E.: Exact algorithms and APX-hardness results for geometric set cover. In: Proc. 23rd Canad. Conf. Comput. Geom., CCCG (2011)"},{"key":"60_CR12","doi-asserted-by":"publisher","first-page":"373","DOI":"10.1007\/s00454-012-9417-5","volume":"48","author":"T.M. Chan","year":"2012","unstructured":"Chan, T.M., Har-Peled, S.: Approximation algorithms for maximum independent set of pseudo-disks. Discrete Comput. Geom.\u00a048, 373\u2013392 (2012)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"60_CR13","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"K.L. Clarkson","year":"2007","unstructured":"Clarkson, K.L., Varadarajan, K.R.: Improved approximation algorithms for geometric set cover. Discrete Comput. Geom.\u00a037(1), 43\u201358 (2007)","journal-title":"Discrete Comput. Geom."},{"key":"60_CR14","doi-asserted-by":"publisher","first-page":"275","DOI":"10.1007\/s004530010020","volume":"27","author":"D. Eppstein","year":"2000","unstructured":"Eppstein, D.: Diameter and treewidth in minor-closed graph families. Algorithmica\u00a027, 275\u2013291 (2000)","journal-title":"Algorithmica"},{"key":"60_CR15","doi-asserted-by":"crossref","unstructured":"Feder, T., Greene, D.H.: Optimal algorithms for approximate clustering. In: Proc. 20th Annu. ACM Sympos. Theory Comput., STOC, pp. 434\u2013444 (1988)","DOI":"10.1145\/62212.62255"},{"issue":"6","key":"60_CR16","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1137\/0216064","volume":"16","author":"G.N. Frederickson","year":"1987","unstructured":"Frederickson, G.N.: Fast algorithms for shortest paths in planar graphs, with applications. SIAM J. Comput.\u00a016(6), 1004\u20131022 (1987)","journal-title":"SIAM J. Comput."},{"issue":"4","key":"60_CR17","doi-asserted-by":"publisher","first-page":"613","DOI":"10.1007\/s00493-003-0037-9","volume":"23","author":"M. Grohe","year":"2003","unstructured":"Grohe, M.: Local tree-width, excluded minors, and approximation algorithms. Combinatorica\u00a023(4), 613\u2013632 (2003)","journal-title":"Combinatorica"},{"key":"60_CR18","doi-asserted-by":"crossref","unstructured":"Grohe, M., Kreutzer, S., Siebertz, S.: Deciding first-order properties of nowhere dense graphs. In: Proc. 46th Annu. ACM Sympos. Theory Comput., STOC, pp. 89\u201398 (2014)","DOI":"10.1145\/2591796.2591851"},{"key":"60_CR19","unstructured":"Har-Peled, S.: Being fat and friendly is not enough. CoRR, abs\/0908.2369 (2009)"},{"key":"60_CR20","doi-asserted-by":"crossref","unstructured":"Har-Peled, S.: Quasi-polynomial time approximation scheme for sparse subsets of polygons. In: Proc. 30th Annu. Sympos. Comput. Geom., SoCG, pp. 120\u2013129 (2014)","DOI":"10.1145\/2582112.2582157"},{"key":"60_CR21","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for low-density graphs. CoRR, abs\/1501.00721 (2015), http:\/\/arxiv.org\/abs\/1501.00721"},{"key":"60_CR22","doi-asserted-by":"crossref","unstructured":"Hastad, J.: Clique is hard to approximate within n 1\u2009\u2212\u2009\u03b5 . In: Proc. 37th Annu. IEEE Sympos. Found. Comput. Sci., FOCS, pp. 627\u2013636 (1996)","DOI":"10.1109\/SFCS.1996.548522"},{"key":"60_CR23","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1006\/jcss.1997.1493","volume":"55","author":"M.R. Henzinger","year":"1997","unstructured":"Henzinger, M.R., Klein, P., Rao, S., Subramanian, S.: Faster shortest-path algorithms for planar graphs. J. Comput. Sys. Sci.\u00a055, 3\u201323 (1997)","journal-title":"J. Comput. Sys. Sci."},{"key":"60_CR24","doi-asserted-by":"crossref","unstructured":"Karp, R.M.: Reducibility among combinatorial problems. In: Complexity of Computer Computations, pp. 85\u2013103 (1972)","DOI":"10.1007\/978-1-4684-2001-2_9"},{"key":"60_CR25","unstructured":"Koebe, P.: Kontaktprobleme der konformen Abbildung. Ber. Verh. S\u00e4chs. Akademie der Wissenschaften Leipzig, Math.-Phys. Klasse\u00a088, 141\u2013164 (1936)"},{"key":"60_CR26","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"R.J. Lipton","year":"1979","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math.\u00a036, 177\u2013189 (1979)","journal-title":"SIAM J. Appl. Math."},{"issue":"3","key":"60_CR27","doi-asserted-by":"publisher","first-page":"615","DOI":"10.1137\/0209046","volume":"9","author":"R.J. Lipton","year":"1980","unstructured":"Lipton, R.J., Tarjan, R.E.: Applications of a planar separator theorem. SIAM J. Comput.\u00a09(3), 615\u2013627 (1980)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"60_CR28","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1017\/S0963548313000400","volume":"23","author":"J. Matou\u0161ek","year":"2014","unstructured":"Matou\u0161ek, J.: Near-optimal separators in string graphs. Combin., Prob. & Comput.\u00a023(1), 135\u2013139 (2014)","journal-title":"Combin., Prob. & Comput."},{"issue":"1","key":"60_CR29","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.P., Vavasis, S.A.: Separators for sphere-packings and nearest neighbor graphs. J. Assoc. Comput. Mach.\u00a044(1), 1\u201329 (1997)","journal-title":"J. Assoc. Comput. Mach."},{"key":"60_CR30","unstructured":"Mustafa, N.H., Raman, R., Ray, S.: QPTAS for geometric set-cover problems via optimal separators. ArXiv e-prints (2014)"},{"key":"60_CR31","doi-asserted-by":"crossref","unstructured":"Mustafa, N.H., Raman, R., Ray, S.: Settling the APX-hardness status for geometric set cover. In: Proc. 55th Annu. IEEE Sympos. Found. Comput. Sci., FOCS (2014) (page to appear)","DOI":"10.1109\/FOCS.2014.64"},{"issue":"4","key":"60_CR32","doi-asserted-by":"publisher","first-page":"883","DOI":"10.1007\/s00454-010-9285-9","volume":"44","author":"N.H. Mustafa","year":"2010","unstructured":"Mustafa, N.H., Ray, S.: Improved results on geometric hitting set problems. Discrete Comput. Geom.\u00a044(4), 883\u2013895 (2010)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"60_CR33","doi-asserted-by":"publisher","first-page":"760","DOI":"10.1016\/j.ejc.2006.07.013","volume":"29","author":"J. Nesetril","year":"2008","unstructured":"Nesetril, J., Ossona de Mendez, P.: Grad and classes with bounded expansion I. Decompositions. Eur. J. Comb.\u00a029(3), 760\u2013776 (2008)","journal-title":"Decompositions. Eur. J. Comb."},{"issue":"3","key":"60_CR34","first-page":"777","volume":"29","author":"J. Nesetril","year":"2008","unstructured":"Nesetril, J., Ossona de Mendez, P.: Grad and classes with bounded expansion II. Algorithmic Aspects\u00a029(3), 777\u2013791 (2008)","journal-title":"Algorithmic Aspects"},{"key":"60_CR35","doi-asserted-by":"crossref","unstructured":"Nesetril, J., Ossona de Mendez, P.: Sparsity. Alg. Combin., vol.\u00a028. Springer (2012)","DOI":"10.1007\/978-3-642-27875-4"},{"key":"60_CR36","doi-asserted-by":"crossref","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. John Wiley & Sons (1995)","DOI":"10.1002\/9781118033203"},{"key":"60_CR37","doi-asserted-by":"crossref","unstructured":"Raz, R., Safra, S.: A sub-constant error-probability low-degree test, and a sub-constant error-probability PCP characterization of NP. In: Proc. 29th Annu. ACM Sympos. Theory Comput., STOC, pp. 475\u2013484 (1997)","DOI":"10.1145\/258533.258641"},{"key":"60_CR38","unstructured":"Schwartz, J.T., Sharir, M.: Efficient motion planning algorithms in environments of bounded local complexity. Report 164, Dept, Math. Sci., New York Univ., New York (1985)"},{"key":"60_CR39","unstructured":"van der Stappen, A.F.: Motion Planning Amidst Fat Obstacles. PhD thesis, Utrecht University, Netherlands (1992)"},{"issue":"4","key":"60_CR40","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/PL00009402","volume":"20","author":"A.F. Stappen van der","year":"1998","unstructured":"van der Stappen, A.F., Overmars, M.H., de Berg, M., Vleugels, J.: Motion planning in environments with low obstacle density. Discrete Comput. Geom.\u00a020(4), 561\u2013587 (1998)","journal-title":"Discrete Comput. Geom."},{"issue":"1","key":"60_CR41","doi-asserted-by":"publisher","first-page":"143","DOI":"10.1007\/s00454-004-2916-2","volume":"33","author":"J.-L. Verger-Gaugry","year":"2005","unstructured":"Verger-Gaugry, J.-L.: Covering a ball with smaller equal balls in \u211d n . Discrete Comput. Geom.\u00a033(1), 143\u2013155 (2005)","journal-title":"Discrete Comput. Geom."}],"container-title":["Lecture Notes in Computer Science","Algorithms - ESA 2015"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48350-3_60","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,30]],"date-time":"2025-05-30T09:57:09Z","timestamp":1748599029000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48350-3_60"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662483497","9783662483503"],"references-count":41,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48350-3_60","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}