{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,9,8]],"date-time":"2024-09-08T23:45:45Z","timestamp":1725839145704},"publisher-location":"Berlin, Heidelberg","reference-count":20,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662489703"},{"type":"electronic","value":"9783662489710"}],"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-48971-0_37","type":"book-chapter","created":{"date-parts":[[2015,11,25]],"date-time":"2015-11-25T23:00:57Z","timestamp":1448492457000},"page":"429-441","source":"Crossref","is-referenced-by-count":2,"title":["Colored Non-crossing Euclidean Steiner Forest"],"prefix":"10.1007","author":[{"given":"Sergey","family":"Bereg","sequence":"first","affiliation":[]},{"given":"Krzysztof","family":"Fleszar","sequence":"additional","affiliation":[]},{"given":"Philipp","family":"Kindermann","sequence":"additional","affiliation":[]},{"given":"Sergey","family":"Pupyrev","sequence":"additional","affiliation":[]},{"given":"Joachim","family":"Spoerhase","sequence":"additional","affiliation":[]},{"given":"Alexander","family":"Wolff","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2015,11,27]]},"reference":[{"issue":"5","key":"37_CR1","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1145\/290179.290180","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S.: Polynomial time approximation schemes for Euclidean traveling salesman and other geometric problems. J. ACM 45(5), 753\u2013782 (1998)","journal-title":"J. ACM"},{"key":"37_CR2","unstructured":"Bastert, O., Fekete, S.P.: Geometric wire routing. Technical report. 96.247, Universit\u00e4t zu K\u00f6ln (1998). \n                      http:\/\/e-archive.informatik.uni-koeln.de\/247"},{"key":"37_CR3","unstructured":"Bereg, S., Fleszar, K., Kindermann, P., Pupyrev, S., Spoerhase, J., Wolff, A.: Colored non-crossing Euclidean steiner forest. CoRR abs\/1509.05681 (2015). \n                      http:\/\/arxiv.org\/abs\/1509.05681"},{"issue":"3","key":"37_CR4","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1145\/1541885.1541892","volume":"5","author":"G Borradaile","year":"2009","unstructured":"Borradaile, G., Klein, P., Mathieu, C.: An \n                      \n                        \n                      \n                      $${O}(n \\log n)$$\n                     approximation scheme for Steiner tree in planar graphs. ACM Trans. Algorithms 5(3), 31 (2009)","journal-title":"ACM Trans. Algorithms"},{"key":"37_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"376","DOI":"10.1007\/978-3-319-03841-4_33","volume-title":"Graph Drawing","author":"TM Chan","year":"2013","unstructured":"Chan, T.M., Hoffmann, H.-F., Kiazyk, S., Lubiw, A.: Minimum length embedding of planar graphs at fixed vertex locations. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 376\u2013387. Springer, Heidelberg (2013)"},{"issue":"1","key":"37_CR6","doi-asserted-by":"publisher","first-page":"328","DOI":"10.1111\/j.1749-6632.1985.tb14564.x","volume":"440","author":"FRK Chung","year":"1985","unstructured":"Chung, F.R.K., Graham, R.L.: A new bound for Euclidean Steiner minimal trees. Ann. New York Acad. Sci. 440(1), 328\u2013346 (1985)","journal-title":"Ann. New York Acad. Sci."},{"key":"37_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"452","DOI":"10.1007\/978-3-662-45803-7_38","volume-title":"Graph Drawing","author":"A Efrat","year":"2014","unstructured":"Efrat, A., Hu, Y., Kobourov, S.G., Pupyrev, S.: MapSets: visualizing embedded and clustered graphs. In: Duncan, C., Symvonis, A. (eds.) GD 2014. LNCS, vol. 8871, pp. 452\u2013463. Springer, Heidelberg (2014)"},{"issue":"3","key":"37_CR8","doi-asserted-by":"publisher","first-page":"162","DOI":"10.1016\/j.comgeo.2006.03.003","volume":"35","author":"A Efrat","year":"2006","unstructured":"Efrat, A., Kobourov, S.G., Lubiw, A.: Computing homotopic shortest paths efficiently. Comput. Geom. Theory Appl. 35(3), 162\u2013172 (2006)","journal-title":"Comput. Geom. Theory Appl."},{"key":"37_CR9","doi-asserted-by":"crossref","unstructured":"Erickson, J., Nayyeri, A.: Shortest non-crossing walks in the plane. In: Proceedings of ACM-SIAM Symposium on Discrete Algorithms (SODA 2011), pp. 297\u2013308 (2011)","DOI":"10.1137\/1.9781611973082.25"},{"key":"37_CR10","volume-title":"Computers and Intractability: A Guide to the Theory of NP-Completeness","author":"MR Garey","year":"1979","unstructured":"Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman & Co., New York (1979)"},{"key":"37_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"280","DOI":"10.1007\/978-3-319-03841-4_25","volume-title":"Graph Drawing","author":"F Hurtado","year":"2013","unstructured":"Hurtado, F., Korman, M., van Kreveld, M., L\u00f6ffler, M., Sacrist\u00e1n, V., Silveira, R.I., Speckmann, B.: Colored spanning graphs for set visualization. In: Wismath, S., Wolff, A. (eds.) GD 2013. LNCS, vol. 8242, pp. 280\u2013291. Springer, Heidelberg (2013)"},{"key":"37_CR12","doi-asserted-by":"publisher","first-page":"249","DOI":"10.1023\/A:1011425821069","volume":"5","author":"Y Kusakari","year":"2001","unstructured":"Kusakari, Y., Masubuchi, D., Nishizeki, T.: Finding a noncrossing Steiner forest in plane graphs under a 2-face condition. J. Combin. Optim. 5, 249\u2013266 (2001)","journal-title":"J. Combin. Optim."},{"issue":"1","key":"37_CR13","doi-asserted-by":"publisher","first-page":"84","DOI":"10.1287\/ijoc.7.1.84","volume":"7","author":"TM Liebling","year":"1995","unstructured":"Liebling, T.M., Margot, F., M\u00fcller, D., Prodon, A., Stauffer, L.: Disjoint paths in the plane. ORSA J. Comput. 7(1), 84\u201388 (1995)","journal-title":"ORSA J. Comput."},{"issue":"1","key":"37_CR14","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1142\/S0218195911003524","volume":"21","author":"M L\u00f6ffler","year":"2011","unstructured":"L\u00f6ffler, M.: Existence and computation of tours through imprecise points. Int. J. Comput. Geom. Appl. 21(1), 1\u201324 (2011)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"37_CR15","doi-asserted-by":"publisher","first-page":"1298","DOI":"10.1137\/S0097539796309764","volume":"28","author":"JS Mitchell","year":"1999","unstructured":"Mitchell, J.S.: Guillotine subdivisions approximate polygonal subdivisions: a simple polynomial-time approximation scheme for geometric TSP, \n                      \n                        \n                      \n                      $$k$$\n                    -MST, and related problems. SIAM J. Comput. 28(4), 1298\u20131309 (1999)","journal-title":"SIAM J. Comput."},{"key":"37_CR16","doi-asserted-by":"crossref","unstructured":"Mitchell, J.S.: Geometric shortest paths and network optimization. In: Urrutia, J., Sack, J.R. (eds.) Handbook of Computational Geometry, chap. 15, pp. 633\u2013701. North-Holland (2000)","DOI":"10.1016\/B978-044482537-7\/50016-4"},{"issue":"4","key":"37_CR17","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1016\/j.comgeo.2009.01.011","volume":"43","author":"M M\u00fcller-Hannemann","year":"2010","unstructured":"M\u00fcller-Hannemann, M., Tazari, S.: A near linear time approximation scheme for Steiner tree among obstacles in the plane. Comput. Geom. Theory Appl. 43(4), 395\u2013409 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"6","key":"37_CR18","doi-asserted-by":"publisher","first-page":"533","DOI":"10.1142\/S0218195999000315","volume":"9","author":"E Papadopoulou","year":"1999","unstructured":"Papadopoulou, E.: \n                      \n                        \n                      \n                      $$k$$\n                    -pairs non-crossing shortest paths in a simple polygon. Int. J. Comput. Geom. Appl. 9(6), 533\u2013552 (1999)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"37_CR19","doi-asserted-by":"crossref","unstructured":"Polishchuk, V., Mitchell, J.S.B.: Thick non-crossing paths and minimum-cost flows in polygonal domains. In: Proceedings of the ACM Symposium on Computational Geometry (SoCG 2007), pp. 56\u201365 (2007)","DOI":"10.1145\/1247069.1247079"},{"key":"37_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/978-3-642-36763-2_24","volume-title":"Graph Drawing","author":"K Verbeek","year":"2013","unstructured":"Verbeek, K.: Homotopic \n                      \n                        \n                      \n                      $$\\cal {C}$$\n                    -oriented routing. In: Didimo, W., Patrignani, M. (eds.) GD 2012. LNCS, vol. 7704, pp. 272\u2013278. Springer, Heidelberg (2013)"}],"container-title":["Lecture Notes in Computer Science","Algorithms and Computation"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-48971-0_37","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,5,31]],"date-time":"2019-05-31T13:50:38Z","timestamp":1559310638000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-48971-0_37"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015]]},"ISBN":["9783662489703","9783662489710"],"references-count":20,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-48971-0_37","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2015]]}}}