Vertex-colored encompassing graphs. (English) Zbl 1298.05120

Summary: It is shown that every disconnected vertex-colored plane straight line graph with no isolated vertices can be augmented (by adding edges) into a connected plane straight line graph such that the new edges respect the coloring and the degree of every vertex increases by at most two. The upper bound for the increase of vertex degrees is best possible: there are input graphs that require the addition of two new edges incident to a vertex. The exclusion of isolated vertices is necessary: there are input graphs with isolated vertices that cannot be augmented to a connected vertex-colored plane straight line graph.


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


[1] Akiyama J., Urrutia J.: Simple alternating path problem. Discrete Math. 84, 101-103 (1990) · Zbl 0699.05032 · doi:10.1016/0012-365X(90)90276-N
[2] de Berg M., Cheong O., van Kreveld M., Overmars M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008) · Zbl 1140.68069 · doi:10.1007/978-3-540-77974-2
[3] Borgelt M.G., van Kreveld M., Löffler M., Luo J., Merrick D., Silveira R.I., 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
[4] Bose P., Gudmundsson J., Smid M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42, 249-264 (2005) · Zbl 1086.68136 · doi:10.1007/s00453-005-1168-8
[5] Bose P., Houle M.E., Toussaint G.T.: Every set of disjoint line segments admits a binary tree. Discrete Comput. Geom. 26, 387-410 (2001) · Zbl 0988.68140 · doi:10.1007/s00454-001-0042-y
[6] Bose P., Toussaint G.T.: Growing a tree from its branches. J. Algorithms 19, 86-103 (1995) · Zbl 0836.68078 · doi:10.1006/jagm.1995.1028
[7] Grantson, M., Meijer, H., Rappaport, D.: Bi-chromatic minimum spanning trees. In: Abstracts of 21st European Workshop on Computational Geometry, Eindhoven, pp. 199-202 (2005) · Zbl 0545.90098
[8] 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-233 (1987) · Zbl 0642.68081 · doi:10.1007/BF01840360
[9] Hoffmann M., Speckmann B., Tóth Cs.D.: Pointed binary encompassing trees: simple and optimal. Comput. Geom. Theory Appl. 43, 35-41 (2010) · Zbl 1200.05147 · doi:10.1016/j.comgeo.2006.12.005
[10] Hoffmann M., Tóth Cs.D.: Alternating paths through disjoint line segments. Inf. Proc. Lett. 87, 287-294 (2003) · Zbl 1161.68818 · doi:10.1016/S0020-0190(03)00349-1
[11] Hoffmann M., Tóth Cs.D.: Segment endpoint visibility graphs are Hamiltonian. Comput. Geom. Theory Appl. 26, 47-68 (2003) · Zbl 1024.68111 · doi:10.1016/S0925-7721(02)00172-4
[12] Hurtado F., Kano M., Rappaport D., Tóth Cs.D.: Encompassing colored crossing-free geometric graphs. Comput. Geom. Theory Appl. 39, 14-23 (2008) · Zbl 1124.05034 · doi:10.1016/j.comgeo.2007.05.006
[13] Ishaque, M., Tóth, Cs.D.: Relative convex hulls in semi-dynamic arrangements. Algorithmica (2012, in print) · Zbl 1317.68250
[14] Kaneko, A.: On the maximum degree of bipartite embeddings of trees in the plane. In: Akiyama, M. et al. (eds.) Discrete and Computational Geometry. Japan Conference on Discrete and Computational Geometry 1998. LNCS, vol. 1763, pp. 166-171. Springer, Berlin (2000) · Zbl 0959.05033
[15] Kaneko, A., Kano. M.: Discrete geometry on red and blue points in the plane—a survey. In: Discrete and Computational Geometry, The Goodman-Pollack Festschrift. Algorithms and Combinatorics, vol. 25, pp. 551-570. Springer, Berlin (2003) · Zbl 1079.52505
[16] Kaneko, A., Kano, M.: On paths in a complete bipartite geometric graph. In: Akiyama, M. et al. (eds.) Discrete and Computational Geometry. Japan Conference on Discrete and Computational Geometry 2000. LNCS, vol. 2098, pp. 187-191. Springer, Berlin (2001) · Zbl 0991.05064
[17] Kaneko A., Kano M., Yoshimoto K.: Alternating Hamiltonian cycles with minimum number of crossings in the plane. Int. J. Comput. Geom. Appl. 10, 73-78 (2000) · Zbl 1074.68640
[18] Lee D.T., Lin A.K.: Generalized Delaunay triangulations for planar graphs. Discrete Comput. Geom. 1, 201-217 (1986) · Zbl 0596.52007 · doi:10.1007/BF02187695
[19] Lee D.T., Preparata F.P.: Euclidean shortest path in the presence of rectilinear barriers. Networks 14, 393-410 (1984) · Zbl 0545.90098 · doi:10.1002/net.3230140304
[20] Souvaine D.L., Tóth Cs.D.: A vertex-face assignment for plane graphs. Comput. Geom. Theory Appl. 42(5), 388-394 (2009) · Zbl 1169.05357 · doi:10.1016/j.comgeo.2008.06.005
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.