{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T11:30:13Z","timestamp":1725795013896},"publisher-location":"Cham","reference-count":21,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319066851"},{"type":"electronic","value":"9783319066868"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2014]]},"DOI":"10.1007\/978-3-319-06686-8_26","type":"book-chapter","created":{"date-parts":[[2014,6,2]],"date-time":"2014-06-02T01:30:40Z","timestamp":1401672640000},"page":"337-350","source":"Crossref","is-referenced-by-count":0,"title":["Crossing-Free Spanning Trees in Visibility Graphs of Points between Monotone Polygonal Obstacles"],"prefix":"10.1007","author":[{"given":"Julia","family":"Sch\u00fcler","sequence":"first","affiliation":[]},{"given":"Andreas","family":"Spillner","sequence":"additional","affiliation":[]}],"member":"297","reference":[{"key":"26_CR1","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s00454-009-9233-8","volume":"44","author":"H. Alpert","year":"2010","unstructured":"Alpert, H., Koch, C., Laison, J.: Obstacle numbers of graphs. Discrete & Computational Geometry\u00a044, 223\u2013244 (2010)","journal-title":"Discrete & Computational Geometry"},{"key":"26_CR2","doi-asserted-by":"publisher","first-page":"1631","DOI":"10.1137\/S0097539704446384","volume":"36","author":"B. Ben-Moshe","year":"2007","unstructured":"Ben-Moshe, B., Katz, M., Mitchell, J.: A constant-factor approximation algorithm for optimal 1.5D terrain guarding. SIAM Journal on Computing\u00a036, 1631\u20131647 (2007)","journal-title":"SIAM Journal on Computing"},{"key":"26_CR3","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1016\/S0925-7721(00)00011-0","volume":"16","author":"Q. Cheng","year":"2000","unstructured":"Cheng, Q., Chrobak, M., Sundaram, G.: Computing simple paths among obstacles. Computational Geometry\u00a016, 223\u2013233 (2000)","journal-title":"Computational Geometry"},{"key":"26_CR4","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s00454-006-1273-8","volume":"37","author":"K. Clarkson","year":"2007","unstructured":"Clarkson, K., Varadarajan, K.: Improved approximation algorithms for geometric set cover. Discrete & Computational Geometry\u00a037, 43\u201358 (2007)","journal-title":"Discrete & Computational Geometry"},{"key":"26_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1007\/978-3-540-89550-3_5","volume-title":"Computational Geometry and Graph Theory","author":"O. Daescu","year":"2008","unstructured":"Daescu, O., Luo, J.: Computing simple paths on points in simple polygons. In: Ito, H., Kano, M., Katoh, N., Uno, Y. (eds.) KyotoCGGT 2007. LNCS, vol.\u00a04535, pp. 41\u201355. Springer, Heidelberg (2008)"},{"key":"26_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/3-540-49381-6_45","volume-title":"Algorithms and Computation","author":"S. Eidenbenz","year":"1998","unstructured":"Eidenbenz, S.: Inapproximability results for guarding polygons without holes. In: Chwa, K.-Y., Ibarra, O.H. (eds.) ISAAC 1998. LNCS, vol.\u00a01533, pp. 427\u2013436. Springer, Heidelberg (1998)"},{"key":"26_CR7","doi-asserted-by":"publisher","first-page":"451","DOI":"10.1007\/s00453-009-9358-4","volume":"60","author":"K. Elbassioni","year":"2011","unstructured":"Elbassioni, K., Krohn, E., Matijevi\u0107, D., Mestre, J., \u0160everdija, D.: Improved approximations for guarding 1.5-dimensional terrains. Algorithmica\u00a060, 451\u2013463 (2011)","journal-title":"Algorithmica"},{"key":"26_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"140","DOI":"10.1007\/978-3-642-03685-9_11","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"M. Gibson","year":"2009","unstructured":"Gibson, M., Kanade, G., Krohn, E., Varadarajan, K.: An approximation scheme for terrain guarding. In: Dinur, I., Jansen, K., Naor, J., Rolim, J. (eds.) APPROX and RANDOM 2009. LNCS, vol.\u00a05687, pp. 140\u2013148. Springer, Heidelberg (2009)"},{"key":"26_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/978-3-540-73951-7_36","volume-title":"Algorithms and Data Structures","author":"M. Halld\u00f3rsson","year":"2007","unstructured":"Halld\u00f3rsson, M., Knauer, C., Spillner, A., Tokuyama, T.: Fixed-parameter tractability for non-crossing spanning trees. In: Dehne, F., Sack, J.-R., Zeh, N. (eds.) WADS 2007. LNCS, vol.\u00a04619, pp. 410\u2013421. Springer, Heidelberg (2007)"},{"key":"26_CR10","doi-asserted-by":"publisher","first-page":"580","DOI":"10.1007\/BF01990536","volume":"33","author":"K. Jansen","year":"1993","unstructured":"Jansen, K., Woeginger, G.: The complexity of detecting crossingfree configurations in the plane. BIT\u00a033, 580\u2013595 (1993)","journal-title":"BIT"},{"key":"26_CR11","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/PL00009317","volume":"18","author":"G. K\u00e1rolyi","year":"1997","unstructured":"K\u00e1rolyi, G., Pach, J., T\u00f3th, G.: Ramsey-type results for geometric graphs I. Discrete & Computational Geometry\u00a018, 247\u2013255 (1997)","journal-title":"Discrete & Computational Geometry"},{"key":"26_CR12","doi-asserted-by":"crossref","unstructured":"Keller, C., Perles, M., Rivera-Campo, E., Urrutia-Galicia, V.: Blockers for noncrossing spanning trees in complete geometric graphs. In: Pach, J. (ed.) Thirty Essays on Geometric Graph Theory, pp. 383\u2013397. Springer (2013)","DOI":"10.1007\/978-1-4614-0110-0_20"},{"key":"26_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"629","DOI":"10.1007\/11682462_58","volume-title":"LATIN 2006: Theoretical Informatics","author":"J. King","year":"2006","unstructured":"King, J.: A 4-approximation algorithm for guarding 1.5-dimensional terrains. In: Correa, J.R., Hevia, A., Kiwi, M. (eds.) LATIN 2006. LNCS, vol.\u00a03887, pp. 629\u2013640. Springer, Heidelberg (2006)"},{"key":"26_CR14","doi-asserted-by":"publisher","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 Journal on Computing\u00a040, 1316\u20131339 (2011)","journal-title":"SIAM Journal on Computing"},{"key":"26_CR15","doi-asserted-by":"publisher","first-page":"104","DOI":"10.1016\/j.comgeo.2006.06.001","volume":"37","author":"C. Knauer","year":"2007","unstructured":"Knauer, C., Schramm, \u00c9., Spillner, A., Wolff, A.: Configurations with few crossings in topological graphs. Computational Geometry\u00a037, 104\u2013114 (2007)","journal-title":"Computational Geometry"},{"key":"26_CR16","unstructured":"Koch, A., Krug, M., Rutter, I.: Graphs with plane outside-obstacle representations (2013) available online: arXiv:1306.2978"},{"key":"26_CR17","unstructured":"Krohn, E., Nilsson, B.: The complexity of guarding monotone polygons. In: Proc. Canadian Conference on Computational Geoemtry, pp. 167\u2013172 (2012)"},{"key":"26_CR18","doi-asserted-by":"publisher","first-page":"564","DOI":"10.1007\/s00453-012-9653-3","volume":"66","author":"E. Krohn","year":"2013","unstructured":"Krohn, E., Nilsson, B.: Approximate guarding of monotone and rectilinear polygons. Algorithmica\u00a066, 564\u2013594 (2013)","journal-title":"Algorithmica"},{"key":"26_CR19","doi-asserted-by":"crossref","unstructured":"Mukkamala, P., Pach, J., P\u00e1lv\u00f6lgyi, D.: Lower bounds on the obstacle number of graphs. The Electronic Journal of Combinatorics 19 (2012)","DOI":"10.37236\/2380"},{"key":"26_CR20","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/s00373-011-1027-0","volume":"27","author":"J. Pach","year":"2011","unstructured":"Pach, J., Sar\u0131\u00f6z, D.: On the structure of graphs with low obstacle number. Graphs and Combinatorics\u00a027, 465\u2013473 (2011)","journal-title":"Graphs and Combinatorics"},{"key":"26_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"274","DOI":"10.1007\/978-3-540-46515-7_24","volume-title":"Discrete and Computational Geometry","author":"E. Rivera-Campo","year":"2000","unstructured":"Rivera-Campo, E.: A note on the existente of plane spanning trees of geometrie graphs. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 1998. LNCS, vol.\u00a01763, pp. 274\u2013277. Springer, Heidelberg (2000)"}],"container-title":["Lecture Notes in Computer Science","Computer Science - Theory and Applications"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-06686-8_26","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,8,20]],"date-time":"2020-08-20T07:49:00Z","timestamp":1597909740000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-06686-8_26"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014]]},"ISBN":["9783319066851","9783319066868"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-06686-8_26","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2014]]}}}