{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,7,20]],"date-time":"2025-07-20T04:28:02Z","timestamp":1752985682370},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2013,5,16]],"date-time":"2013-05-16T00:00:00Z","timestamp":1368662400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2014,7]]},"DOI":"10.1007\/s00373-013-1320-1","type":"journal-article","created":{"date-parts":[[2013,5,15]],"date-time":"2013-05-15T08:37:47Z","timestamp":1368607067000},"page":"933-947","source":"Crossref","is-referenced-by-count":6,"title":["Vertex-Colored Encompassing Graphs"],"prefix":"10.1007","volume":"30","author":[{"given":"Michael","family":"Hoffmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2013,5,16]]},"reference":[{"key":"1320_CR1","doi-asserted-by":"crossref","first-page":"101","DOI":"10.1016\/0012-365X(90)90276-N","volume":"84","author":"J. Akiyama","year":"1990","unstructured":"Akiyama J., Urrutia J.: Simple alternating path problem. Discrete Math. 84, 101\u2013103 (1990)","journal-title":"Discrete Math."},{"key":"1320_CR2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-540-77974-2","volume-title":"Computational Geometry: Algorithms and Applications","author":"M. Berg de","year":"2008","unstructured":"de Berg M., Cheong O., van Kreveld M., Overmars M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)","edition":"3"},{"key":"1320_CR3","doi-asserted-by":"crossref","first-page":"469","DOI":"10.1016\/j.jda.2008.08.001","volume":"7","author":"M.G. 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, 469\u2013478 (2009)","journal-title":"J. Discrete Algorithms"},{"key":"1320_CR4","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/s00453-005-1168-8","volume":"42","author":"P. Bose","year":"2005","unstructured":"Bose P., Gudmundsson J., Smid M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42, 249\u2013264 (2005)","journal-title":"Algorithmica"},{"key":"1320_CR5","doi-asserted-by":"crossref","first-page":"387","DOI":"10.1007\/s00454-001-0042-y","volume":"26","author":"P. Bose","year":"2001","unstructured":"Bose P., Houle M.E., Toussaint G.T.: Every set of disjoint line segments admits a binary tree. Discrete Comput. Geom. 26, 387\u2013410 (2001)","journal-title":"Discrete Comput. Geom."},{"key":"1320_CR6","doi-asserted-by":"crossref","first-page":"86","DOI":"10.1006\/jagm.1995.1028","volume":"19","author":"P. Bose","year":"1995","unstructured":"Bose P., Toussaint G.T.: Growing a tree from its branches. J. Algorithms 19, 86\u2013103 (1995)","journal-title":"J. Algorithms"},{"key":"1320_CR7","unstructured":"Grantson, M., Meijer, H., Rappaport, D.: Bi-chromatic minimum spanning trees. In: Abstracts of 21st European Workshop on Computational Geometry, Eindhoven, pp. 199\u2013202 (2005)"},{"key":"1320_CR8","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L.J. Guibas","year":"1987","unstructured":"Guibas L.J., Hershberger J., Leven D., Sharir M., Tarjan R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2, 209\u2013233 (1987)","journal-title":"Algorithmica"},{"key":"1320_CR9","doi-asserted-by":"crossref","first-page":"35","DOI":"10.1016\/j.comgeo.2006.12.005","volume":"43","author":"M. Hoffmann","year":"2010","unstructured":"Hoffmann M., Speckmann B., T\u00f3th Cs.D.: Pointed binary encompassing trees: simple and optimal. Comput. Geom. Theory Appl. 43, 35\u201341 (2010)","journal-title":"Comput. Geom. Theory Appl."},{"key":"1320_CR10","doi-asserted-by":"crossref","first-page":"287","DOI":"10.1016\/S0020-0190(03)00349-1","volume":"87","author":"M. Hoffmann","year":"2003","unstructured":"Hoffmann M., T\u00f3th Cs.D.: Alternating paths through disjoint line segments. Inf. Proc. Lett. 87, 287\u2013294 (2003)","journal-title":"Inf. Proc. Lett."},{"key":"1320_CR11","doi-asserted-by":"crossref","first-page":"47","DOI":"10.1016\/S0925-7721(02)00172-4","volume":"26","author":"M. Hoffmann","year":"2003","unstructured":"Hoffmann M., T\u00f3th Cs.D.: Segment endpoint visibility graphs are Hamiltonian. Comput. Geom. Theory Appl. 26, 47\u201368 (2003)","journal-title":"Comput. Geom. Theory Appl."},{"key":"1320_CR12","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 Cs.D.: Encompassing colored crossing-free geometric graphs. Comput. Geom. Theory Appl. 39, 14\u201323 (2008)","journal-title":"Comput. Geom. Theory Appl."},{"key":"1320_CR13","doi-asserted-by":"crossref","unstructured":"Ishaque, M., T\u00f3th, Cs.D.: Relative convex hulls in semi-dynamic arrangements. Algorithmica (2012, in print)","DOI":"10.1007\/s00453-012-9679-6"},{"key":"1320_CR14","doi-asserted-by":"crossref","unstructured":"Kaneko, A.: On the maximum degree of bipartite embeddings of trees in the plane. In: Akiyama, M. et\u00a0al. (eds.) Discrete and Computational Geometry. Japan Conference on Discrete and Computational Geometry 1998. LNCS, vol. 1763, pp. 166\u2013171. Springer, Berlin (2000)","DOI":"10.1007\/978-3-540-46515-7_13"},{"key":"1320_CR15","doi-asserted-by":"crossref","unstructured":"Kaneko, A., Kano. M.: Discrete geometry on red and blue points in the plane\u2014a survey. In: Discrete and Computational Geometry, The Goodman-Pollack Festschrift. Algorithms and Combinatorics, vol. 25, pp. 551\u2013570. Springer, Berlin (2003)","DOI":"10.1007\/978-3-642-55566-4_25"},{"key":"1320_CR16","doi-asserted-by":"crossref","unstructured":"Kaneko, A., Kano, M.: On paths in a complete bipartite geometric graph. In: Akiyama, M. et\u00a0al. (eds.) Discrete and Computational Geometry. Japan Conference on Discrete and Computational Geometry 2000. LNCS, vol. 2098, pp. 187\u2013191. Springer, Berlin (2001)","DOI":"10.1007\/3-540-47738-1_17"},{"key":"1320_CR17","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1142\/S021819590000005X","volume":"10","author":"A. Kaneko","year":"2000","unstructured":"Kaneko A., Kano M., Yoshimoto K.: Alternating Hamiltonian cycles with minimum number of crossings in the plane. Int. J. Comput. Geom. Appl. 10, 73\u201378 (2000)","journal-title":"Int. J. Comput. Geom. Appl."},{"key":"1320_CR18","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF02187695","volume":"1","author":"D.T. Lee","year":"1986","unstructured":"Lee D.T., Lin A.K.: Generalized Delaunay triangulations for planar graphs. Discrete Comput. Geom. 1, 201\u2013217 (1986)","journal-title":"Discrete Comput. Geom."},{"key":"1320_CR19","doi-asserted-by":"crossref","first-page":"393","DOI":"10.1002\/net.3230140304","volume":"14","author":"D.T. Lee","year":"1984","unstructured":"Lee D.T., Preparata F.P.: Euclidean shortest path in the presence of rectilinear barriers. Networks 14, 393\u2013410 (1984)","journal-title":"Networks"},{"issue":"5","key":"1320_CR20","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1016\/j.comgeo.2008.06.005","volume":"42","author":"D.L. Souvaine","year":"2009","unstructured":"Souvaine D.L., T\u00f3th Cs.D.: A vertex-face assignment for plane graphs. Comput. Geom. Theory Appl. 42(5), 388\u2013394 (2009)","journal-title":"Comput. Geom. Theory Appl."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-013-1320-1.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-013-1320-1\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-013-1320-1","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,26]],"date-time":"2020-07-26T19:31:21Z","timestamp":1595791881000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-013-1320-1"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,5,16]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7]]}},"alternative-id":["1320"],"URL":"https:\/\/doi.org\/10.1007\/s00373-013-1320-1","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"value":"0911-0119","type":"print"},{"value":"1435-5914","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,5,16]]}}}