{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,14]],"date-time":"2026-02-14T02:33:02Z","timestamp":1771036382891,"version":"3.50.1"},"reference-count":30,"publisher":"Springer Science and Business Media LLC","issue":"6","license":[{"start":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T00:00:00Z","timestamp":1665792000000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T00:00:00Z","timestamp":1665792000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100003246","name":"Nederlandse Organisatie voor Wetenschappelijk Onderzoek","doi-asserted-by":"publisher","award":["NETWORKS-024.002.003"],"award-info":[{"award-number":["NETWORKS-024.002.003"]}],"id":[{"id":"10.13039\/501100003246","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2023,6]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:italic>F<\/jats:italic> be a set of <jats:italic>n<\/jats:italic> objects in the plane and let <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {G}^{\\times }(F)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>G<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mo>\u00d7<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>F<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> be its intersection graph. A balanced clique-based separator of <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {G}^{\\times }(F)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>G<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mo>\u00d7<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>F<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> is a set <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {\\mathcal {S}}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mi>S<\/mml:mi>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> consisting of cliques whose removal partitions <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {G}^{\\times }(F)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>G<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mo>\u00d7<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>F<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> into components of size at most <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta n$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, for some fixed constant <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\delta &lt;1$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>\u03b4<\/mml:mi>\n                    <mml:mo>&lt;<\/mml:mo>\n                    <mml:mn>1<\/mml:mn>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. The weight of a clique-based separator is defined as <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\sum _{C\\in \\mathcal {\\mathcal {S}}}\\log (|C|+1)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msub>\n                      <mml:mo>\u2211<\/mml:mo>\n                      <mml:mrow>\n                        <mml:mi>C<\/mml:mi>\n                        <mml:mo>\u2208<\/mml:mo>\n                        <mml:mi>S<\/mml:mi>\n                      <\/mml:mrow>\n                    <\/mml:msub>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mi>C<\/mml:mi>\n                      <mml:mo>|<\/mml:mo>\n                      <mml:mo>+<\/mml:mo>\n                      <mml:mn>1<\/mml:mn>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. Recently De\u00a0Berg\u00a0et al. (SIAM J. Comput. 49: 1291-1331. 2020) proved that if <jats:italic>S<\/jats:italic> consists of convex fat objects, then <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\mathcal {G}^{\\times }(F)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:msup>\n                      <mml:mrow>\n                        <mml:mi>G<\/mml:mi>\n                      <\/mml:mrow>\n                      <mml:mo>\u00d7<\/mml:mo>\n                    <\/mml:msup>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>F<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> admits a balanced clique-based separator of weight\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We extend this result in several directions, obtaining the following results. (i) Map graphs admit a balanced clique-based separator of weight\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n})$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is tight in the worst case. (ii) Intersection graphs of pseudo-disks admit a balanced clique-based separator of weight\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^{2\/3}\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. If the pseudo-disks are polygonal and of total complexity\u00a0<jats:italic>O<\/jats:italic>(<jats:italic>n<\/jats:italic>) then the weight of the separator improves to\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n}\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. (iii) Intersection graphs of geodesic disks inside a simple polygon admit a balanced clique-based separator of weight\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(n^{2\/3}\\log n)$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msup>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mrow>\n                        <mml:mn>2<\/mml:mn>\n                        <mml:mo>\/<\/mml:mo>\n                        <mml:mn>3<\/mml:mn>\n                      <\/mml:mrow>\n                    <\/mml:msup>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. (iv) Visibility-restricted unit-disk graphs in a polygonal domain with <jats:italic>r<\/jats:italic> reflex vertices admit a balanced clique-based separator of weight\u00a0<jats:inline-formula><jats:alternatives><jats:tex-math>$$O(\\sqrt{n}+r\\log (n\/r))$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>O<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:msqrt>\n                      <mml:mi>n<\/mml:mi>\n                    <\/mml:msqrt>\n                    <mml:mo>+<\/mml:mo>\n                    <mml:mi>r<\/mml:mi>\n                    <mml:mo>log<\/mml:mo>\n                    <mml:mrow>\n                      <mml:mo>(<\/mml:mo>\n                      <mml:mi>n<\/mml:mi>\n                      <mml:mo>\/<\/mml:mo>\n                      <mml:mi>r<\/mml:mi>\n                      <mml:mo>)<\/mml:mo>\n                    <\/mml:mrow>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>, which is tight in the worst case. These results immediately imply sub-exponential algorithms for <jats:sc>Maximum Independent Set<\/jats:sc> (and, hence, <jats:sc>Vertex Cover<\/jats:sc>), for <jats:sc>Feedback Vertex Set<\/jats:sc>, and for <jats:italic>q<\/jats:italic>-<jats:sc>Coloring<\/jats:sc> for constant\u00a0<jats:italic>q<\/jats:italic> in these graph classes.<\/jats:p>","DOI":"10.1007\/s00453-022-01041-8","type":"journal-article","created":{"date-parts":[[2022,10,15]],"date-time":"2022-10-15T08:03:01Z","timestamp":1665820981000},"page":"1652-1678","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Clique-Based Separators for Geometric Intersection Graphs"],"prefix":"10.1007","volume":"85","author":[{"given":"Mark","family":"de Berg","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"S\u00e1ndor","family":"Kisfaludi-Bak","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Morteza","family":"Monemizadeh","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1707-6787","authenticated-orcid":false,"given":"Leonidas","family":"Theocharous","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,10,15]]},"reference":[{"issue":"2","key":"1041_CR1","doi-asserted-by":"publisher","first-page":"543","DOI":"10.1137\/120891241","volume":"43","author":"B Aronov","year":"2014","unstructured":"Aronov, B., de Berg, M.T., Ezra, E., Sharir, M.: Improved bounds for the union of locally fat objects in the plane. SIAM J. Comput. 43(2), 543\u2013572 (2014). https:\/\/doi.org\/10.1137\/120891241","journal-title":"SIAM J. Comput."},{"key":"1041_CR2","doi-asserted-by":"publisher","unstructured":"Ben-Moshe, B., Hall-Holt, O., Katz, M.J., Mitchell, J.S.: Computing the visibility graph of points within a polygon. In: Proc. 20th ACM Symposium on Computational Geometry, pp. 27\u201335. ACM (2004). https:\/\/doi.org\/10.1145\/997817.997825","DOI":"10.1145\/997817.997825"},{"key":"1041_CR3","doi-asserted-by":"publisher","first-page":"86","DOI":"10.1016\/j.ic.2014.12.008","volume":"243","author":"HL Bodlaender","year":"2015","unstructured":"Bodlaender, H.L., Cygan, M., Kratsch, S., Nederlof, J.: Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. Inf. Comput. 243, 86\u2013111 (2015). https:\/\/doi.org\/10.1016\/j.ic.2014.12.008","journal-title":"Inf. Comput."},{"issue":"7","key":"1041_CR4","doi-asserted-by":"publisher","first-page":"3047","DOI":"10.1007\/s00453-019-00568-7","volume":"81","author":"\u00c9 Bonnet","year":"2019","unstructured":"Bonnet, \u00c9., Rzazewski, P.: Optimality program in segment and string graphs. Algorithmica 81(7), 3047\u20133073 (2019). https:\/\/doi.org\/10.1007\/s00453-019-00568-7","journal-title":"Algorithmica"},{"key":"1041_CR5","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1023\/A:1005003212822","volume":"71","author":"M Breen","year":"1998","unstructured":"Breen, M.: A Helly-type theorem for intersections of compact connected sets in the plane. Geom. Dedic. 71, 111\u2013117 (1998). https:\/\/doi.org\/10.1023\/A:1005003212822","journal-title":"Geom. Dedic."},{"issue":"2","key":"1041_CR6","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1016\/S0196-6774(02)00294-8","volume":"46","author":"TM Chan","year":"2003","unstructured":"Chan, T.M.: Polynomial-time approximation schemes for packing and piercing fat objects. J. Algorithms 46(2), 178\u2013189 (2003). https:\/\/doi.org\/10.1016\/S0196-6774(02)00294-8","journal-title":"J. Algorithms"},{"issue":"1","key":"1041_CR7","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1006\/jagm.2001.1178","volume":"41","author":"ZZ Chen","year":"2001","unstructured":"Chen, Z.Z.: Approximation algorithms for independent sets in map graphs. J. Algorithms 41(1), 20\u201340 (2001). https:\/\/doi.org\/10.1006\/jagm.2001.1178","journal-title":"J. Algorithms"},{"issue":"2","key":"1041_CR8","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1145\/506147.506148","volume":"49","author":"ZZ Chen","year":"2002","unstructured":"Chen, Z.Z., Grigni, M., Papadimitriou, C.H.: Map graphs. J. ACM 49(2), 127\u2013138 (2002). https:\/\/doi.org\/10.1145\/506147.506148","journal-title":"J. ACM"},{"key":"1041_CR9","doi-asserted-by":"publisher","first-page":"387","DOI":"10.1007\/BF02187740","volume":"4","author":"KL Clarkson","year":"1989","unstructured":"Clarkson, K.L., Shor, P.W.: Application of random sampling in computational geometry, II. Discret. Comput. Geom. 4, 387\u2013421 (1989). https:\/\/doi.org\/10.1007\/BF02187740","journal-title":"Discret. Comput. Geom."},{"key":"1041_CR10","doi-asserted-by":"publisher","unstructured":"de\u00a0Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S., Kolay, S.: An ETH-tight exact algorithm for euclidean TSP. In: 59th IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 450\u2013461 (2018). https:\/\/doi.org\/10.1109\/FOCS.2018.00050","DOI":"10.1109\/FOCS.2018.00050"},{"key":"1041_CR11","doi-asserted-by":"publisher","first-page":"1291","DOI":"10.1137\/20M1320870","volume":"49","author":"M de Berg","year":"2020","unstructured":"de Berg, M., Bodlaender, H.L., Kisfaludi-Bak, S., Marx, D., van der Zanden, T.C.: A framework for Exponential-Time-Hypothesis-tight algorithms and lower bounds in geometric intersection graphs. SIAM J. Comput. 49, 1291\u20131331 (2020). https:\/\/doi.org\/10.1137\/20M1320870","journal-title":"SIAM J. Comput."},{"key":"1041_CR12","doi-asserted-by":"crossref","unstructured":"de\u00a0Berg, M., Cheong, O., van Kreveld, M.J., Overmars, M. H.: Computational geometry: algorithms and applications (3rd Ed). Springer, (2008). URL: https:\/\/www.worldcat.org\/oclc\/227584184","DOI":"10.1007\/978-3-540-77974-2"},{"issue":"3","key":"1041_CR13","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1007\/s002360050082","volume":"34","author":"H Djidjev","year":"1997","unstructured":"Djidjev, H., Venkatesan, S.M.: Reduced constants for simple cycle graph separation. Acta Inform. 34(3), 231\u2013243 (1997). https:\/\/doi.org\/10.1007\/s002360050082","journal-title":"Acta Inform."},{"key":"1041_CR14","doi-asserted-by":"publisher","unstructured":"Fomin, F. V., Lokshtanov, D., Panolan, F., Saurabh, S., Zehavi, M.: Decomposition of map graphs with applications. In: Proc.\u00a046th International Colloquium on Automata, Languages, and Programming, (ICALP), pp. 60:1\u201360:15, (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2019.60","DOI":"10.4230\/LIPIcs.ICALP.2019.60"},{"issue":"1","key":"1041_CR15","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.jctb.2009.03.005","volume":"100","author":"J Fox","year":"2010","unstructured":"Fox, J., Pach, J., T\u00f3th, C.D.: A bipartite strengthening of the crossing lemma. J. Comb. Theory Ser. B 100(1), 23\u201335 (2010). https:\/\/doi.org\/10.1016\/j.jctb.2009.03.005","journal-title":"J. Comb. Theory Ser. B"},{"issue":"6","key":"1041_CR16","doi-asserted-by":"publisher","first-page":"1712","DOI":"10.1137\/16M1079336","volume":"46","author":"S Har-Peled","year":"2017","unstructured":"Har-Peled, S., Quanrud, K.: Approximation algorithms for polynomial-expansion and low-density graphs. SIAM J. Comput. 46(6), 1712\u20131744 (2017). https:\/\/doi.org\/10.1137\/16M1079336","journal-title":"SIAM J. Comput."},{"key":"1041_CR17","doi-asserted-by":"publisher","first-page":"59","DOI":"10.1007\/BF02187683","volume":"1","author":"K Kedem","year":"1986","unstructured":"Kedem, K., Livne, R., Pach, J., Sharir, M.: On the union of Jordan regions and collision-free translational motion amidst polygonal obstacles. Discret. Comput. Geom. 1, 59\u201370 (1986). https:\/\/doi.org\/10.1007\/BF02187683","journal-title":"Discret. Comput. Geom."},{"key":"1041_CR18","doi-asserted-by":"publisher","unstructured":"Kisfaludi-Bak, S.: Hyperbolic intersection graphs and (quasi)-polynomial time. In: Proc. 31st ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 1621\u20131638 (2020). https:\/\/doi.org\/10.1137\/1.9781611975994.100","DOI":"10.1137\/1.9781611975994.100"},{"key":"1041_CR19","doi-asserted-by":"publisher","unstructured":"Kisfaludi-Bak, S., Marx, D., van\u00a0der Zanden, T. C.: How does object fatness impact the complexity of packing in $$d$$ dimensions? In: 30th International Symposium on Algorithms and Computation, ISAAC 2019, vol. 149 of LIPIcs, pp. 36:1\u201336:18 (2019). https:\/\/doi.org\/10.4230\/LIPIcs.ISAAC.2019.36","DOI":"10.4230\/LIPIcs.ISAAC.2019.36"},{"key":"1041_CR20","doi-asserted-by":"publisher","unstructured":"Lee, J. R.: Separators in region intersection graphs. In: 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, vol.\u00a067 of LIPIcs, pp. 1:1\u20131:8 (2017). https:\/\/doi.org\/10.4230\/LIPIcs.ITCS.2017.1","DOI":"10.4230\/LIPIcs.ITCS.2017.1"},{"issue":"2","key":"1041_CR21","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1137\/0136016","volume":"36","author":"RJ Lipton","year":"1977","unstructured":"Lipton, R.J., Tarjan, R.E.: A separator theorem for planar graphs. SIAM J. Appl. Math. 36(2), 177\u2013189 (1977). https:\/\/doi.org\/10.1137\/0136016","journal-title":"SIAM J. Appl. Math."},{"key":"1041_CR22","doi-asserted-by":"publisher","unstructured":"Marx, D., Pilipczuk, M.: Optimal parameterized algorithms for planar facility location problems using voronoi diagrams. In Proc.\u00a023rd Annual European Symposium on Algorithms (ESA), vol. 9294 of Lecture Notes in Computer Science, pp. 865\u2013877. Springer (2015). https:\/\/doi.org\/10.1007\/978-3-662-48350-3_72","DOI":"10.1007\/978-3-662-48350-3_72"},{"key":"1041_CR23","doi-asserted-by":"publisher","unstructured":"Matousek, J.: Lectures on Discrete Geometry, vol. 212 of Graduate Texts in Mathematics, pp. 14\u201316. Springer (2002). https:\/\/doi.org\/10.1007\/978-1-4613-0039-7","DOI":"10.1007\/978-1-4613-0039-7"},{"issue":"1","key":"1041_CR24","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. Comb. Probab. Comput. 23(1), 135\u2013139 (2014). https:\/\/doi.org\/10.1017\/S0963548313000400","journal-title":"Comb. Probab. Comput."},{"issue":"1","key":"1041_CR25","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/256292.256294","volume":"44","author":"GL 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. ACM 44(1), 1\u201329 (1997). https:\/\/doi.org\/10.1145\/256292.256294","journal-title":"J. ACM"},{"key":"1041_CR26","doi-asserted-by":"publisher","unstructured":"Pach, J., Sharir, M.: Geometric incidences. In: Pach, J. (ed) Towards a Theory of Geometric Graphs, Contemporary Mathematics, vol. 342, pp. 185\u2013223. American Mathematical Society (2004). https:\/\/doi.org\/10.1090\/conm\/342","DOI":"10.1090\/conm\/342"},{"key":"1041_CR27","doi-asserted-by":"publisher","first-page":"1930","DOI":"10.1137\/130949750","volume":"28","author":"R Pinchasi","year":"2014","unstructured":"Pinchasi, R.: A finite family of pseudodiscs must include a \u201csmall\u2019\u2019 pseudodisc. SIAM J. Discret. Math. 28, 1930\u20131934 (2014). https:\/\/doi.org\/10.1137\/130949750","journal-title":"SIAM J. Discret. Math."},{"issue":"6","key":"1041_CR28","doi-asserted-by":"publisher","first-page":"611","DOI":"10.1007\/BF02187751","volume":"4","author":"Ricky Pollack","year":"1989","unstructured":"Pollack, Ricky, Sharir, Micha, Rote, G\u00fcnter.: Computing the geodesic center of a simple polygon. Discret. Comput. Geom. 4(6), 611\u2013626 (1989). https:\/\/doi.org\/10.1007\/BF02187751","journal-title":"Discret. Comput. Geom."},{"key":"1041_CR29","doi-asserted-by":"publisher","first-page":"1098","DOI":"10.1007\/s00454-020-00216-w","volume":"64","author":"R Raman","year":"2020","unstructured":"Raman, R., Ray, S.: Constructing planar support for non-piercing regions. Discret. Comput. Geom. 64, 1098\u20131122 (2020)","journal-title":"Discret. Comput. Geom."},{"key":"1041_CR30","doi-asserted-by":"publisher","unstructured":"Smith, W. D., Wormald, N. C.: Geometric separator theorems & applications. In: 39th Annual Symposium on Foundations of Computer Science (FOCS), pp. 232\u2013243. IEEE Computer Society (1998). https:\/\/doi.org\/10.1109\/SFCS.1998.743449","DOI":"10.1109\/SFCS.1998.743449"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01041-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s00453-022-01041-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-022-01041-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,5,27]],"date-time":"2023-05-27T03:34:37Z","timestamp":1685158477000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s00453-022-01041-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,10,15]]},"references-count":30,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2023,6]]}},"alternative-id":["1041"],"URL":"https:\/\/doi.org\/10.1007\/s00453-022-01041-8","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,10,15]]},"assertion":[{"value":"7 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"26 August 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 October 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}