{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:37:33Z","timestamp":1759639053446,"version":"3.37.3"},"reference-count":25,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T00:00:00Z","timestamp":1489104000000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"funder":[{"DOI":"10.13039\/501100002790","name":"Canadian Network for Research and Innovation in Machining Technology, Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100002790","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Discrete Comput Geom"],"published-print":{"date-parts":[[2018,6]]},"DOI":"10.1007\/s00454-017-9881-z","type":"journal-article","created":{"date-parts":[[2017,3,10]],"date-time":"2017-03-10T14:27:17Z","timestamp":1489156037000},"page":"864-885","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":5,"title":["Plane Bichromatic Trees of Low Degree"],"prefix":"10.1007","volume":"59","author":[{"given":"Ahmad","family":"Biniaz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Prosenjit","family":"Bose","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Anil","family":"Maheshwari","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Michiel","family":"Smid","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2017,3,10]]},"reference":[{"key":"9881_CR1","doi-asserted-by":"crossref","unstructured":"Abellanas, M., Garc\u00eda, J., Hern\u00e1ndez, G., Noy, M., Ramos, P.: Bipartite embeddings of trees in the plane. In: North, S. (ed.) Graph Drawing. Lecture Notes in Computer Science, vol. 1190, pp. 1\u201310. Springer, Berlin (1996)","DOI":"10.1007\/3-540-62495-3_33"},{"issue":"2\u20133","key":"9881_CR2","doi-asserted-by":"crossref","first-page":"141","DOI":"10.1016\/S0166-218X(99)00042-6","volume":"93","author":"M Abellanas","year":"1999","unstructured":"Abellanas, M., Garc\u00eda, J., Hern\u00e1ndez, G., Noy, M., Ramos, P.: Bipartite embeddings of trees in the plane. Discrete Appl. Math. 93(2\u20133), 141\u2013148 (1999)","journal-title":"Discrete Appl. Math."},{"issue":"5","key":"9881_CR3","doi-asserted-by":"crossref","first-page":"449","DOI":"10.1007\/BF02187805","volume":"5","author":"PK Agarwal","year":"1990","unstructured":"Agarwal, P.K.: Partitioning arrangements of lines I. An efficient deterministic algorithm. Discrete Comput. Geom. 5(5), 449\u2013483 (1990)","journal-title":"Discrete Comput. Geom."},{"issue":"5","key":"9881_CR4","doi-asserted-by":"crossref","first-page":"407","DOI":"10.1007\/BF02574698","volume":"6","author":"PK Agarwal","year":"1991","unstructured":"Agarwal, P.K., Edelsbrunner, H., Schwarzkopf, O., Welzl, E.: Euclidean minimum spanning trees and bichromatic closest pairs. Discrete Comput. Geom. 6(5), 407\u2013422 (1991)","journal-title":"Discrete Comput. Geom."},{"issue":"3","key":"9881_CR5","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/s00453-004-1103-4","volume":"40","author":"S Arora","year":"2004","unstructured":"Arora, S., Chang, K.: Approximation schemes for degree-restricted MST and red\u2013blue separation problems. Algorithmica 40(3), 189\u2013210 (2004)","journal-title":"Algorithmica"},{"issue":"4","key":"9881_CR6","doi-asserted-by":"crossref","first-page":"373","DOI":"10.1142\/S0218195901000547","volume":"11","author":"MJ Atallah","year":"2001","unstructured":"Atallah, M.J., Chen, D.Z.: On connecting red and blue rectilinear polygonal obstacles with nonintersecting monotone rectilinear paths. Int. J. Comput. Geom. Appl. 11(4), 373\u2013400 (2001)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"9881_CR7","doi-asserted-by":"crossref","first-page":"605","DOI":"10.1007\/s4540010065","volume":"24","author":"S Bespamyatnikh","year":"2000","unstructured":"Bespamyatnikh, S., Kirkpatrick, D., Snoeyink, J.: Generalizing ham sandwich cuts to equitable subdivisions. Discrete Comput. Geom. 24(4), 605\u2013622 (2000)","journal-title":"Discrete Comput. Geom."},{"key":"9881_CR8","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1016\/j.comgeo.2016.05.004","volume":"57","author":"A Biniaz","year":"2016","unstructured":"Biniaz, A., Bose, P., Maheshwari, A., Smid, M.: Plane geodesic spanning trees, Hamiltonian cycles, and perfect matchings in a simple polygon. Comput. Geom. 57, 27\u201339 (2016)","journal-title":"Comput. Geom."},{"issue":"1","key":"9881_CR9","doi-asserted-by":"crossref","first-page":"41","DOI":"10.1142\/S0218195900000036","volume":"10","author":"J-D Boissonnat","year":"2000","unstructured":"Boissonnat, J.-D., Czyzowicz, J., Devillers, O., Urrutia, J., Yvinec, M.: Computing largest circles separating two sets of segments. Int. J. Comput. Geom. Appl. 10(1), 41\u201353 (2000)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"9881_CR10","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1016\/j.jda.2008.08.001","volume":"7","author":"MG Borgelt","year":"2009","unstructured":"Borgelt, M.G., van Kreveld, M., L\u00f6ffler, M., Luo, J., Merrick, D., Silveira, R.I., Vahedi, M.: Planar bichromatic minimum spanning trees. J. Discrete Algorithms 7(4), 469\u2013478 (2009)","journal-title":"J. Discrete Algorithms"},{"issue":"2","key":"9881_CR11","doi-asserted-by":"crossref","first-page":"1","DOI":"10.7155\/jgaa.00002","volume":"1","author":"P Bose","year":"1997","unstructured":"Bose, P., McAllister, M., Snoeyink, J.: Optimal algorithms to embed trees in a point set. J. Graph Algorithms Appl. 1(2), 1\u201315 (1997)","journal-title":"J. Graph Algorithms Appl."},{"issue":"4","key":"9881_CR12","doi-asserted-by":"crossref","first-page":"403","DOI":"10.1142\/S0218195905001762","volume":"15","author":"ED Demaine","year":"2005","unstructured":"Demaine, E.D., Erickson, J., Hurtado, F., Iacono, J., Langerman, S., Meijer, H., Overmars, M., Whitesides, S.: Separating point sets in polygonal environments. Int. J. Comput. Geom. Appl. 15(4), 403\u2013419 (2005)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"3","key":"9881_CR13","doi-asserted-by":"crossref","first-page":"247","DOI":"10.1142\/S0218195996000186","volume":"6","author":"H Everett","year":"1996","unstructured":"Everett, H., Robert, J.-M., van Kreveld, M.: An optimal algorithm for computing ( $$\\le k$$ \u2264 k )-levels, with applications. Int. J. Comput. Geom. Appl. 6(3), 247\u2013261 (1996)","journal-title":"Int. J. Comput. Geom. Appl."},{"issue":"4","key":"9881_CR14","doi-asserted-by":"crossref","first-page":"933","DOI":"10.1007\/s00373-013-1320-1","volume":"30","author":"M Hoffmann","year":"2014","unstructured":"Hoffmann, M., T\u00f3th, C.D.: Vertex-colored encompassing graphs. Graphs Comb. 30(4), 933\u2013947 (2014)","journal-title":"Graphs Comb."},{"issue":"1","key":"9881_CR15","doi-asserted-by":"crossref","first-page":"14","DOI":"10.1016\/j.comgeo.2007.05.006","volume":"39","author":"F Hurtado","year":"2008","unstructured":"Hurtado, F., Kano, M., Rappaport, D., T\u00f3th, C.D.: Encompassing colored planar straight line graphs. Comput. Geom. 39(1), 14\u201323 (2008)","journal-title":"Comput. Geom."},{"issue":"1\u20132","key":"9881_CR16","doi-asserted-by":"crossref","first-page":"109","DOI":"10.1016\/S0166-218X(00)00230-4","volume":"109","author":"F Hurtado","year":"2001","unstructured":"Hurtado, F., Noy, M., Ramos, P.A., Seara, C.: Separating objects in the plane by wedges and strips. Discrete Appl. Math. 109(1\u20132), 109\u2013138 (2001)","journal-title":"Discrete Appl. Math."},{"issue":"1","key":"9881_CR17","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1007\/BF02573994","volume":"11","author":"Y Ikebe","year":"1994","unstructured":"Ikebe, Y., Perles, M.A., Tamura, A., Tokunaga, S.: The rooted tree embedding problem into points in the plane. Discrete Comput. Geom. 11(1), 51\u201363 (1994)","journal-title":"Discrete Comput. Geom."},{"key":"9881_CR18","doi-asserted-by":"crossref","unstructured":"Kaneko, A.: On the maximum degree of bipartite embeddings of trees in the plane. In: Discrete and Computational Geometry. Lecture Notes in Computer Science, vol. 1763, pp. 166\u2013171. Springer, Berlin (2000)","DOI":"10.1007\/978-3-540-46515-7_13"},{"key":"9881_CR19","doi-asserted-by":"crossref","first-page":"551","DOI":"10.1007\/978-3-642-55566-4_25","volume-title":"Discrete and Computational Geometry. Algorithms and Combinatorics","author":"A Kaneko","year":"2003","unstructured":"Kaneko, A., Kano, M.: Discrete geometry on red and blue points in the plane\u2014a survey. In: Aronov, B., et al. (eds.) Discrete and Computational Geometry. Algorithms and Combinatorics, vol. 25, pp. 551\u2013570. Springer, Berlin (2003)"},{"issue":"1","key":"9881_CR20","doi-asserted-by":"crossref","first-page":"P1.13","DOI":"10.37236\/3628","volume":"22","author":"M Kano","year":"2015","unstructured":"Kano, M., Ozeki, K., Suzuki, K., Tsugaki, M., Yamashita, T.: Spanning k-trees of bipartite graphs. Electron. J. Comb. 22(1), P1.13 (2015)","journal-title":"Electron. J. Comb."},{"key":"9881_CR21","doi-asserted-by":"crossref","unstructured":"Kano, M., Suzuki, K., Uno, M.: Properly colored geometric matchings and 3-trees without crossings on multicolored points in the plane. In: Akiyama, J., Ito, H., Sakai, T. (eds.) Discrete and Computational Geometry and Graphs. Lecture Notes in Computer Science, vol. 8845, pp. 96\u2013111. Springer, Cham (2014)","DOI":"10.1007\/978-3-319-13287-7_9"},{"key":"9881_CR22","doi-asserted-by":"crossref","unstructured":"Kano, M., Uno, M.: General balanced subdivision of two sets of points in the plane. In: Akiyama, J., et al. (eds.) Discrete Geometry, Combinatorics and Graph Theory. Lecture Notes in Computer Science, vol. 4381, pp. 79\u201387. Springer, Berlin (2007)","DOI":"10.1007\/978-3-540-70666-3_9"},{"key":"9881_CR23","doi-asserted-by":"crossref","first-page":"307","DOI":"10.1007\/978-3-642-83539-1_11","volume-title":"Theoretical Foundations of Computer Graphics and CAD, NATO ASI Series","author":"HG Mairson","year":"1988","unstructured":"Mairson, H.G., Stolfi, J.: Reporting and counting intersections between two sets of line segments. In: Earnshaw, R.A. (ed.) Theoretical Foundations of Computer Graphics and CAD, NATO ASI Series, vol. 40, pp. 307\u2013325. Springer, Berlin (1988)"},{"key":"9881_CR24","doi-asserted-by":"crossref","unstructured":"Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1995)","DOI":"10.1002\/9781118033203"},{"issue":"4","key":"9881_CR25","doi-asserted-by":"crossref","first-page":"211","DOI":"10.1016\/0020-0190(92)90087-C","volume":"44","author":"A Tamura","year":"1992","unstructured":"Tamura, A., Tamura, Y.: Degree constrained tree embedding into points in the plane. Inf. Process. Lett. 44(4), 211\u2013214 (1992)","journal-title":"Inf. Process. Lett."}],"container-title":["Discrete & Computational Geometry"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00454-017-9881-z\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9881-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00454-017-9881-z.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,10,3]],"date-time":"2020-10-03T18:11:55Z","timestamp":1601748715000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00454-017-9881-z"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,3,10]]},"references-count":25,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2018,6]]}},"alternative-id":["9881"],"URL":"https:\/\/doi.org\/10.1007\/s00454-017-9881-z","relation":{},"ISSN":["0179-5376","1432-0444"],"issn-type":[{"type":"print","value":"0179-5376"},{"type":"electronic","value":"1432-0444"}],"subject":[],"published":{"date-parts":[[2017,3,10]]}}}