Abstract
It is known that for any set V of n ≥ 4 points in the plane, not in convex position, there is a 3-connected planar straight line graph G = (V, E) with at most 2n − 2 edges, and this bound is the best possible. We show that the upper bound | E | ≤ 2n continues to hold if G = (V, E) is constrained to contain a given graph G 0 = (V, E 0), which is either a 1-factor (i.e., disjoint line segments) or a 2-factor (i.e., a collection of simple polygons), but no edge in E 0 is a proper diagonal of the convex hull of V. Since there are 1- and 2-factors with n vertices for which any 3-connected augmentation has at least 2n − 2 edges, our bound is nearly tight in these cases. We also examine possible conditions under which this bound may be improved, such as when G 0 is a collection of interior-disjoint convex polygons in a triangular container.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
O. Aichholzer, S. Bereg, A. Dumitrescu, A. García, C. Huemer, F. Hurtado, M. Kano, A. Márquez, D. Rappaport, S. Smorodinsky, D. L. Souvaine, J. Urrutia, D.R. Wood, Compatible geometric matchings. Comput. Geom.: Theor. Appl. 42, 617–626 (2009)
M. Al-Jubeh, M. Ishaque, K. Rédei, D.L. Souvaine, C.D. Tóth, Augmenting the edge connectivity of planar straight line graphs to three. Algorithmica
K.P. Eswaran, R.E. Tarjan, Augmentation problems. SIAM J. Comput. 5, 653–665 (1976)
A. García, F. Hurtado, C. Huemer, J. Tejel, P. Valtr, On triconnected and cubic plane graphs on given point sets. Comput. Geom.: Theor. Appl. 42, 913–922 (2009)
M. Hoffmann, C.D. Tóth, Segment endpoint visibility graphs are Hamiltonian. Comput. Geom.: Theor. Appl. 26, 47–68 (2003)
T.-S. Hsu, V. Ramachandran, On finding a minimum augmentation to biconnect a graph. SIAM J. Comput. 22(5), 889–912 (1993)
T.-S. Hsu, Simpler and faster biconnectivity augmentation. J. Algorithms 45(1), 55–71 (2002)
M. Ishaque, D.L. Souvaine, C.D. Tth, Disjoint compatible geometric matchings, Discrete and Computational Geometry, in print. DOI 10.1007/s00454-012-9466-9 (2012)
B. Jackson, T. Jordán, Independence free graphs and vertex connectivity augmentation. J. Comb. Theor. Ser. B 94, 31–77 (2005)
G. Kant, H.L. Bodlaender, Planar graph augmentation problems, in Proceedings of the 2nd Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol. 519 (Springer-Verlag, Berlin, 1991), pp. 286–298
J. Plesník, Minimum block containing a given graph. Arch. Math. 21, 668–672 (1976)
I. Rutter, A. Wolff, Augmenting the connectivity of planar and geometric graphs. in Proceedings of the International Conference on Topological and Geometric Graph Theory, Paris. Electron. Notes Discr. Math. 31, 53–56 (2008)
C.D. Tóth, P. Valtr, Augmenting the edge connectivity of planar straight line graphs to three, in 13th Spanish Meeting on Computational Geometry, Zaragoza, Spain, 2009
Acknowledgements
We are grateful to the anonymous referee who pointed out several errors and omissions in an earlier version of the proof of Lemma 3.1.
This material is based upon work supported by the National Science Foundation under Grant No. 0830734. Research by C. D. Tóth was also supported by NSERC grant RGPIN 35586. Preliminary results have been presented at the 26th European Workshop on Computational Geometry (2010, Dortmund) and at the 20th Annual Fall Workshop on Computational Geometry (2010, Stony Brook, NY).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2013 Springer Science+Business Media New York
About this chapter
Cite this chapter
Al-Jubeh, M., Barequet, G., Ishaque, M., Souvaine, D.L., Tóth, C.D., Winslow, A. (2013). Constrained Tri-Connected Planar Straight Line Graphs. In: Pach, J. (eds) Thirty Essays on Geometric Graph Theory. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-0110-0_5
Download citation
DOI: https://doi.org/10.1007/978-1-4614-0110-0_5
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-0109-4
Online ISBN: 978-1-4614-0110-0
eBook Packages: Mathematics and StatisticsMathematics and Statistics (R0)