Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Akiyama J., Urrutia J.: Simple alternating path problem. Discrete Math. 84, 101–103 (1990)
de Berg M., Cheong O., van Kreveld M., Overmars M.: Computational Geometry: Algorithms and Applications, 3rd edn. Springer, Berlin (2008)
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)
Bose P., Gudmundsson J., Smid M.: Constructing plane spanners of bounded degree and low weight. Algorithmica 42, 249–264 (2005)
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)
Bose P., Toussaint G.T.: Growing a tree from its branches. J. Algorithms 19, 86–103 (1995)
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)
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)
Hoffmann M., Speckmann B., Tóth Cs.D.: Pointed binary encompassing trees: simple and optimal. Comput. Geom. Theory Appl. 43, 35–41 (2010)
Hoffmann M., Tóth Cs.D.: Alternating paths through disjoint line segments. Inf. Proc. Lett. 87, 287–294 (2003)
Hoffmann M., Tóth Cs.D.: Segment endpoint visibility graphs are Hamiltonian. Comput. Geom. Theory Appl. 26, 47–68 (2003)
Hurtado F., Kano M., Rappaport D., Tóth Cs.D.: Encompassing colored crossing-free geometric graphs. Comput. Geom. Theory Appl. 39, 14–23 (2008)
Ishaque, M., Tóth, Cs.D.: Relative convex hulls in semi-dynamic arrangements. Algorithmica (2012, in print)
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)
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)
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)
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)
Lee D.T., Lin A.K.: Generalized Delaunay triangulations for planar graphs. Discrete Comput. Geom. 1, 201–217 (1986)
Lee D.T., Preparata F.P.: Euclidean shortest path in the presence of rectilinear barriers. Networks 14, 393–410 (1984)
Souvaine D.L., Tóth Cs.D.: A vertex-face assignment for plane graphs. Comput. Geom. Theory Appl. 42(5), 388–394 (2009)
Author information
Authors and Affiliations
Corresponding author
Additional information
Preliminary results (on encompassing trees for vertex-colored plane straight line forests) have been published in the Proceedings of the 21st ACM Symposium on Computational Geometry (Pisa, 2005), ACM Press, 2005, pp. 81–90.
M. Hoffmann is partially supported by the ESF EUROCORES programme EuroGIGA, CRP GraDR and the Swiss National Science Foundation, SNF Project 20GG21-134306.
Rights and permissions
About this article
Cite this article
Hoffmann, M., Tóth, C.D. Vertex-Colored Encompassing Graphs. Graphs and Combinatorics 30, 933–947 (2014). https://doi.org/10.1007/s00373-013-1320-1
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-013-1320-1