×

zbMATH — the first resource for mathematics

Augmenting the connectivity of geometric graphs. (English) Zbl 1147.05308
Summary: Let \(G\) be a connected plane geometric graph with \(n\) vertices. In this paper, we study bounds on the number of edges required to be added to \(G\) to obtain 2-vertex or 2-edge connected plane geometric graphs. In particular, we show that for \(G\) to become 2-edge connected, \(\frac {2n}{3}\) additional edges are required in some cases and that \(\frac {6n}{7}\) additional edges are always sufficient. For the special case of plane geometric trees, these bounds decrease to \(\frac{n}{2}\) and \(\frac{2n}{3}\), respectively.

MSC:
05C85 Graph algorithms (graph-theoretic aspects)
05C40 Connectivity
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Bose, P.; Houle, M.E.; Toussaint, G.T., Every set of disjoint line segments admits a binary tree, Discrete comput. geom., 26, 3, 387-410, (2001) · Zbl 0988.68140
[2] Bose, P.; Morin, P., Competitive online routing in geometric graphs, Theoret. comput. sci., 324, 273-288, (2004) · Zbl 1073.68059
[3] Cheng, E.; Jordán, T., Successive edge-connectivity augmentation problems, Math. program., 84, 577-593, (1999) · Zbl 0939.05052
[4] Demaine, E.D.; O’Rourke, J., Geometric folding algorithms: linkages, origami, polyhedra, (2007), Cambridge University Press · Zbl 1135.52009
[5] Frank, A., Connectivity augmentation of networks: structures and algorithms, Math. program., 84, 3, (1999), (special issue)
[6] Eswaran, K.P.; Tarjan, R.E., Augmentation problems, SIAM J. comput., 5, 653-665, (1976) · Zbl 0346.05112
[7] S. Fialko, T.P. Mutzel, A new approximation algorithm for the planar augmentation problem, in: Proc. Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 1998, pp. 260-269 · Zbl 0929.68082
[8] A. García, F. Hurtado, M. Noy, J. Tejel, Augmenting the connectivity of outerplanar graphs, in: Proc. IX Encuentros de Geometría Computacional, 2001, pp. 203-212 (in Spanish)
[9] Hoffmann, M.; Speckmann, B.; Tóth, C.D., Pointed binary encompassing trees, (), 442-454 · Zbl 1095.68716
[10] Hoffmann, M.; Tóth, C.D., Alternating paths through disjoint line segments, Inform. process. lett., 87, 6, 287-294, (2003) · Zbl 1161.68818
[11] Hoffmann, M.; Tóth, C.D., Pointed and colored binary encompassing trees, (), 81-90 · Zbl 1387.68262
[12] T.S. Hsu, On four-connecting a triconnected graph, in: Proc. 33rd Annual IEEE Symposium on Foundations of Computer Science (FOCS), 1992, pp. 70-79 · Zbl 0918.68074
[13] Hurtado, F.; Kano, M.; Rappaport, D.; Tóth, C.D., Encompassing colored crossing-free geometric graphs, Comput. geom., 39, 14-23, (2008) · Zbl 1124.05034
[14] Jackson, B.; Jordán, T., Independence free graphs and vertex connectivity augmentation, J. combin. theory B, 94, 31-77, (2005) · Zbl 1059.05064
[15] G. Kant, Algorithms for drawing planar graphs, Ph.D. thesis, Dept. of Computer Science, University of Utrecht, 1993
[16] Kant, G., Augmenting outerplanar graphs, J. algorithms, 21, 1-25, (1996) · Zbl 0857.68081
[17] Kortsarz, G.; Nutov, Z., Approximating minimum-cost connectivity problems, (), (Chapter 58)
[18] Nagamochi, H.; Ibaraki, T., Deterministic \(\operatorname{O}(n m)\) time edge-splitting in undirected graphs, J. combinatorial optim., 1, 5-46, (1997) · Zbl 0895.90172
[19] Pach, J., Geometric graph theory, (), 219-238
[20] Rappaport, D., Computing simple circuits from a set of line segments is NP-complete, SIAM J. comput., 18, 6, 1128-1139, (1989) · Zbl 0692.68039
[21] Watanabe, T.; Nakamura, A., Edge-connectivity augmentation problems, J. comput. system sci., 35, 96-144, (1987) · Zbl 0622.68057
[22] Watanabe, T.; Nakamura, A., A smallest augmentation to 3-connect a graph, Disc. appl. math., 28, 183-186, (1990) · Zbl 0752.05036
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.