Plane bichromatic trees of low degree. (English) Zbl 1395.05035

Let \(R\) and \(B\) be two disjoint set of points in the plane such that \(| B|\leq| R|\) and no three points of \(R\cup B\) are collinear. The geometric complete bipartite graph \(K(R, B)\) is the bipartite graph whose vertex set is \(R\cup B\) and whose edge set consists of all straight-line segments connecting a point in \(R\) to a point in \(B\). A bichromatic tree on \(R\cup B\) is a spanning tree of \(K(R, B)\). A plane bichromatic tree is a bichromatic tree whose edges do not intersect in their interior. It is straightforward to show that the plane bichromatic trees always exist; this paper is concerned with the problem of finding such trees with maximum degree as small as possible. By a simple degree count it is clear that \((| R|-1)/| B|+1\) is the best possible upper bound on the maximum degree. The authors show that there is always a plane chromatic tree whose maximum degree is at most \(\max \,\{3, \lceil (|R|-1)/|B|\rceil + 1\}\). This proves two conjectures made by A. Kaneko [Lect. Notes Comput. Sci. 1763, 166–171 (2000; Zbl 0959.05033)], and solves an open problem posed by M. Abellanas et al. [Discrete Appl. Math. 93, No. 2–3, 141–148 (1999; Zbl 0929.05021)]. Furthermore, the authors can compute the aforementioned tree in \(O(nx\mathrm{ polylog}(n))\) time.


05C05 Trees
05C10 Planar graphs; geometric and topological aspects of graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI arXiv


[1] Abellanas, M., García, J., Hernández, 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-10. Springer, Berlin (1996) · Zbl 0929.05021
[2] Abellanas, M; García, J; Hernández, G; Noy, M; Ramos, P, Bipartite embeddings of trees in the plane, Discrete Appl. Math., 93, 141-148, (1999) · Zbl 0929.05021 · doi:10.1016/S0166-218X(99)00042-6
[3] Agarwal, PK, Partitioning arrangements of lines I. an efficient deterministic algorithm, Discrete Comput. Geom., 5, 449-483, (1990) · Zbl 0701.68035 · doi:10.1007/BF02187805
[4] Agarwal, PK; Edelsbrunner, H; Schwarzkopf, O; Welzl, E, Euclidean minimum spanning trees and bichromatic closest pairs, Discrete Comput. Geom., 6, 407-422, (1991) · Zbl 0753.68089 · doi:10.1007/BF02574698
[5] Arora, S; Chang, K, Approximation schemes for degree-restricted MST and red-blue separation problems, Algorithmica, 40, 189-210, (2004) · Zbl 1082.68125 · doi:10.1007/s00453-004-1103-4
[6] Atallah, MJ; Chen, DZ, On connecting red and blue rectilinear polygonal obstacles with nonintersecting monotone rectilinear paths, Int. J. Comput. Geom. Appl., 11, 373-400, (2001) · Zbl 1074.68628 · doi:10.1142/S0218195901000547
[7] Bespamyatnikh, S; Kirkpatrick, D; Snoeyink, J, Generalizing ham sandwich cuts to equitable subdivisions, Discrete Comput. Geom., 24, 605-622, (2000) · Zbl 0966.68156 · doi:10.1007/s4540010065
[8] 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-39, (2016) · Zbl 1378.05024 · doi:10.1016/j.comgeo.2016.05.004
[9] 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, 41-53, (2000) · Zbl 1074.68631 · doi:10.1142/S0218195900000036
[10] Borgelt, MG; Kreveld, M; Löffler, M; Luo, J; Merrick, D; Silveira, RI; Vahedi, M, Planar bichromatic minimum spanning trees, J. Discrete Algorithms, 7, 469-478, (2009) · Zbl 1176.90597 · doi:10.1016/j.jda.2008.08.001
[11] Bose, P; McAllister, M; Snoeyink, J, Optimal algorithms to embed trees in a point set, J. Graph Algorithms Appl., 1, 1-15, (1997) · Zbl 0890.05066 · doi:10.7155/jgaa.00002
[12] Demaine, ED; 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, 403-419, (2005) · Zbl 1104.68116 · doi:10.1142/S0218195905001762
[13] Everett, H; Robert, J-M; Kreveld, M, An optimal algorithm for computing (\(\le k\))-levels, with applications, Int. J. Comput. Geom. Appl., 6, 247-261, (1996) · Zbl 0859.68040 · doi:10.1142/S0218195996000186
[14] Hoffmann, M; Tóth, CD, Vertex-colored encompassing graphs, Graphs Comb., 30, 933-947, (2014) · Zbl 1298.05120 · doi:10.1007/s00373-013-1320-1
[15] Hurtado, F; Kano, M; Rappaport, D; Tóth, CD, Encompassing colored planar straight line graphs, Comput. Geom., 39, 14-23, (2008) · Zbl 1124.05034 · doi:10.1016/j.comgeo.2007.05.006
[16] Hurtado, F; Noy, M; Ramos, PA; Seara, C, Separating objects in the plane by wedges and strips, Discrete Appl. Math., 109, 109-138, (2001) · Zbl 0967.68160 · doi:10.1016/S0166-218X(00)00230-4
[17] Ikebe, Y; Perles, MA; Tamura, A; Tokunaga, S, The rooted tree embedding problem into points in the plane, Discrete Comput. Geom., 11, 51-63, (1994) · Zbl 0791.05027 · doi:10.1007/BF02573994
[18] 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-171. Springer, Berlin (2000) · Zbl 0959.05033
[19] Kaneko, A; Kano, M; Aronov, B (ed.); etal., Discrete geometry on red and blue points in the plane—a survey, No. 25, 551-570, (2003), Berlin · Zbl 1079.52505 · doi:10.1007/978-3-642-55566-4_25
[20] Kano, M; Ozeki, K; Suzuki, K; Tsugaki, M; Yamashita, T, Spanning \(k\)-trees of bipartite graphs, Electron. J. Comb., 22, p1.13, (2015) · Zbl 1305.05046
[21] 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-111. Springer, Cham (2014) · Zbl 1452.05064
[22] 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-87. Springer, Berlin (2007) · Zbl 1149.52302
[23] Mairson, HG; Stolfi, J; Earnshaw, RA (ed.), Reporting and counting intersections between two sets of line segments, No. 40, 307-325, (1988), Berlin · doi:10.1007/978-3-642-83539-1_11
[24] Pach, J., Agarwal, P.K.: Combinatorial Geometry. Wiley-Interscience Series in Discrete Mathematics and Optimization. Wiley, New York (1995) · Zbl 0881.52001
[25] Tamura, A; Tamura, Y, Degree constrained tree embedding into points in the plane, Inf. Process. Lett., 44, 211-214, (1992) · Zbl 0768.68184 · doi:10.1016/0020-0190(92)90087-C
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.