{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,14]],"date-time":"2025-10-14T11:27:32Z","timestamp":1760441252042},"reference-count":18,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,12,30]],"date-time":"2014-12-30T00:00:00Z","timestamp":1419897600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2016,2]]},"DOI":"10.1007\/s00453-014-9965-6","type":"journal-article","created":{"date-parts":[[2014,12,29]],"date-time":"2014-12-29T10:11:26Z","timestamp":1419847886000},"page":"643-663","update-policy":"http:\/\/dx.doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["The Complexity of Separating Points in the Plane"],"prefix":"10.1007","volume":"74","author":[{"given":"Sergio","family":"Cabello","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Panos","family":"Giannopoulos","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"issue":"4","key":"9965_CR1","doi-asserted-by":"crossref","first-page":"1016","DOI":"10.1137\/S0097539794269801","volume":"27","author":"PK Agarwal","year":"1998","unstructured":"Agarwal, P.K., Suri, S.: Surface approximation and geometric partitions. SIAM J. Comput. 27(4), 1016\u20131035 (1998)","journal-title":"SIAM J. Comput."},{"key":"9965_CR2","unstructured":"Alt, H., Cabello, S., Giannopoulos, P., Knauer, C.: Minimum cell connection and separation in line segment arrangements. CoRR abs\/1104.4618 (2011)"},{"key":"9965_CR3","unstructured":"Alt, H., Cabello, S., Giannopoulos, P., Knauer, C.: On some connection problems in straight-line segment arrangements. In: Abstracts of the 27th EuroCG, pp. 27\u201330 (2011)"},{"key":"9965_CR4","doi-asserted-by":"crossref","unstructured":"Bereg, S., Kirkpatrick, D.G.: Approximating barrier resilience in wireless sensor networks. In: Proceedings of 5th ALGOSENSORS, LNCS, vol. 5804, pp. 29\u201340. Springer, Berlin (2009)","DOI":"10.1007\/978-3-642-05434-1_5"},{"issue":"1","key":"9965_CR5","doi-asserted-by":"crossref","first-page":"259","DOI":"10.7155\/jgaa.00145","volume":"11","author":"S Cabello","year":"2007","unstructured":"Cabello, S., Demaine, E.D., Rote, G.: Planar embeddings of graphs with specified edge lengths. J. Graph Algorithms Appl. 11(1), 259\u2013276 (2007)","journal-title":"J. Graph Algorithms Appl."},{"key":"9965_CR6","doi-asserted-by":"crossref","unstructured":"Cabello, S., de Verdi\u00e8re, \u00c9.C., Lazarus, F.: Finding shortest non-trivial cycles in directed graphs on surfaces. In: Proceedings of 26th ACM SoCG, pp. 156\u2013165 (2010)","DOI":"10.1145\/1810959.1810988"},{"key":"9965_CR7","doi-asserted-by":"crossref","unstructured":"Gibson, M., Kanade, G., Varadarajan, K.: On isolating points using disks. In: Proceedings of 19th ESA, LNCS, vol. 6942, pp. 61\u201369. Springer, Berlin (2011)","DOI":"10.1007\/978-3-642-23719-5_6"},{"issue":"5","key":"9965_CR8","doi-asserted-by":"crossref","first-page":"1316","DOI":"10.1137\/100791506","volume":"40","author":"J King","year":"2011","unstructured":"King, J., Krohn, E.: Terrain guarding is NP-hard. SIAM J. Comput. 40(5), 1316\u20131339 (2011)","journal-title":"SIAM J. Comput."},{"issue":"3","key":"9965_CR9","doi-asserted-by":"crossref","first-page":"422","DOI":"10.1137\/0405033","volume":"5","author":"DE Knuth","year":"1992","unstructured":"Knuth, D.E., Raghunathan, A.: The problem of compatible representatives. SIAM J. Discret. Math. 5(3), 422\u2013427 (1992)","journal-title":"SIAM J. Discret. Math."},{"key":"9965_CR10","doi-asserted-by":"crossref","unstructured":"Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. In: Proceedings of 11th MobiCom, pp. 284\u2013298. ACM, London (2005)","DOI":"10.1145\/1080829.1080859"},{"issue":"6","key":"9965_CR11","doi-asserted-by":"crossref","first-page":"817","DOI":"10.1007\/s11276-006-9856-0","volume":"13","author":"S Kumar","year":"2007","unstructured":"Kumar, S., Lai, T.H., Arora, A.: Barrier coverage with wireless sensors. Wirel. Netw. 13(6), 817\u2013834 (2007)","journal-title":"Wirel. Netw."},{"issue":"2","key":"9965_CR12","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1137\/0211025","volume":"11","author":"D Lichtenstein","year":"1982","unstructured":"Lichtenstein, D.: Planar formulae and their uses. SIAM J. Comput. 11(2), 329\u2013343 (1982)","journal-title":"SIAM J. Comput."},{"key":"9965_CR13","volume-title":"Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences","author":"B Mohar","year":"2001","unstructured":"Mohar, B., Thomassen, C.: Graphs on Surfaces, Johns Hopkins Studies in the Mathematical Sciences. John Hopkins University Press, Baltimore (2001)"},{"issue":"2","key":"9965_CR14","doi-asserted-by":"crossref","first-page":"11:1","DOI":"10.1145\/1346330.1346336","volume":"55","author":"W Mulzer","year":"2008","unstructured":"Mulzer, W., Rote, G.: Minimum-weight triangulation is NP-hard. J. ACM 55(2), 11:1\u201311:29 (2008)","journal-title":"J. ACM"},{"key":"9965_CR15","unstructured":"Penninger, R., Vigan, I.: Point set isolation using unit disks is NP-complete. CoRR abs\/1303.2779 (2013)"},{"issue":"2","key":"9965_CR16","doi-asserted-by":"crossref","first-page":"155","DOI":"10.1016\/0095-8956(90)90115-G","volume":"48","author":"C Thomassen","year":"1990","unstructured":"Thomassen, C.: Embeddings of graphs with no short noncontractible cycles. J. Comb. Theory B 48(2), 155\u2013177 (1990)","journal-title":"J. Comb. Theory B"},{"key":"9965_CR17","unstructured":"Tseng, K.C.R.: Resilience of wireless sensor networks. Master\u2019s thesis, The University Of British Columbia (Vancouver) (2011)"},{"key":"9965_CR18","doi-asserted-by":"crossref","unstructured":"Tseng, K.C.R., Kirkpatrick, D.: On barrier resilience of sensor networks. In: Proceedings of 7th ALGOSENSORS, LNCS, vol. 7111, pp. 130\u2013144. Springer, Berlin (2012)","DOI":"10.1007\/978-3-642-28209-6_11"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9965-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-014-9965-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-014-9965-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,28]],"date-time":"2019-05-28T19:47:20Z","timestamp":1559072840000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-014-9965-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":18,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,2]]}},"alternative-id":["9965"],"URL":"https:\/\/doi.org\/10.1007\/s00453-014-9965-6","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,30]]}}}