{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:22:54Z","timestamp":1759638174560},"reference-count":37,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2011,8,3]],"date-time":"2011-08-03T00:00:00Z","timestamp":1312329600000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[2011,12]]},"DOI":"10.1007\/s00453-011-9551-0","type":"journal-article","created":{"date-parts":[[2011,8,2]],"date-time":"2011-08-02T17:18:24Z","timestamp":1312305504000},"page":"971-999","source":"Crossref","is-referenced-by-count":9,"title":["Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three"],"prefix":"10.1007","volume":"61","author":[{"given":"Marwan","family":"Al-Jubeh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mashhood","family":"Ishaque","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Krist\u00f3f","family":"R\u00e9dei","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Diane L.","family":"Souvaine","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Csaba D.","family":"T\u00f3th","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pavel","family":"Valtr","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2011,8,3]]},"reference":[{"issue":"3","key":"9551_CR1","doi-asserted-by":"crossref","first-page":"220","DOI":"10.1016\/j.comgeo.2007.09.001","volume":"40","author":"M. Abellanas","year":"2008","unstructured":"Abellanas,\u00a0M., Garc\u00eda,\u00a0A., Hurtado,\u00a0F., Tejel,\u00a0J., Urrutia,\u00a0J.: Augmenting the connectivity of geometric graphs. Comput. Geom. Theory Appl. 40(3), 220\u2013230 (2008)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"4","key":"9551_CR2","doi-asserted-by":"crossref","first-page":"509","DOI":"10.1109\/TIT.1985.1057060","volume":"IT-31","author":"B. Chazelle","year":"1985","unstructured":"Chazelle,\u00a0B.: On the convex layers of a planar set. IEEE Trans. Inf. Theory IT-31(4), 509\u2013517 (1985)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"9551_CR3","doi-asserted-by":"crossref","first-page":"577","DOI":"10.1007\/s101070050041","volume":"84","author":"E. Cheng","year":"1999","unstructured":"Cheng,\u00a0E., Jord\u00e1n,\u00a0T.: Successive edge-connectivity augmentation problems. Math. Program. 84, 577\u2013593 (1999)","journal-title":"Math. Program."},{"issue":"4","key":"9551_CR4","doi-asserted-by":"crossref","first-page":"653","DOI":"10.1137\/0205044","volume":"5","author":"K.P. Eswaran","year":"1976","unstructured":"Eswaran, K.P., Tarjan, R.E.: Augmentation problems. SIAM J. Comput. 5(4), 653\u2013665 (1976)","journal-title":"SIAM J. Comput."},{"key":"9551_CR5","first-page":"260","volume-title":"Proc. 9th ACM-SIAM Symposium on Discrete Algorithms","author":"S. Fialko","year":"1998","unstructured":"Fialko,\u00a0S., Mutzel,\u00a0P.: A\u00a0new approximation algorithm for the planar augmentation problem. In: Proc. 9th ACM-SIAM Symposium on Discrete Algorithms, pp. 260\u2013269. ACM Press, New York (1998)"},{"issue":"1","key":"9551_CR6","doi-asserted-by":"crossref","first-page":"22","DOI":"10.1137\/0405003","volume":"5","author":"A. Frank","year":"1992","unstructured":"Frank,\u00a0A.: Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5(1), 22\u201353 (1992)","journal-title":"SIAM J. Discrete Math."},{"issue":"1","key":"9551_CR7","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1137\/0222002","volume":"22","author":"Z. Galil","year":"1993","unstructured":"Galil,\u00a0Z., Italiano, G.F.: Maintaining the 3-edge-connected components of a graph on-line. SIAM J. Comput. 22(1), 11\u201328 (1993)","journal-title":"SIAM J. Comput."},{"key":"9551_CR8","doi-asserted-by":"crossref","first-page":"913","DOI":"10.1016\/j.comgeo.2009.03.005","volume":"42","author":"A. Garc\u00eda","year":"2009","unstructured":"Garc\u00eda,\u00a0A., Hurtado,\u00a0F., Huemer,\u00a0C., Tejel,\u00a0J., Valtr,\u00a0P.: On triconnected and cubic plane graphs on given point sets. Comput. Geom. Theory Appl. 42, 913\u2013922 (2009)","journal-title":"Comput. Geom. Theory Appl."},{"issue":"2","key":"9551_CR9","doi-asserted-by":"crossref","first-page":"160","DOI":"10.1007\/s00453-008-9167-1","volume":"56","author":"A. Garc\u00eda","year":"2010","unstructured":"Garc\u00eda,\u00a0A., Hurtado,\u00a0F., Noy,\u00a0M., Tejel,\u00a0J.: Augmenting the connectivity of outerplanar graphs. Algorithmica 56(2), 160\u2013179 (2010)","journal-title":"Algorithmica"},{"key":"9551_CR10","doi-asserted-by":"crossref","first-page":"51","DOI":"10.1006\/jagm.1995.0797","volume":"23","author":"M.T. Goodrich","year":"1997","unstructured":"Goodrich, M.T., Tamassia,\u00a0R.: Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations. J. Algorithms 23, 51\u201373 (1997)","journal-title":"J. Algorithms"},{"key":"9551_CR11","doi-asserted-by":"crossref","first-page":"132","DOI":"10.1016\/0020-0190(72)90045-2","volume":"1","author":"R.L. Graham","year":"1972","unstructured":"Graham, R.L.: An efficient algorithm for determining the convex hull of a finite planar set. Inf. Process. Lett. 1, 132\u2013133 (1972)","journal-title":"Inf. Process. Lett."},{"key":"9551_CR12","doi-asserted-by":"crossref","first-page":"209","DOI":"10.1007\/BF01840360","volume":"2","author":"L. Guibas","year":"1987","unstructured":"Guibas,\u00a0L., Hershberger,\u00a0J., Leven,\u00a0D., Sharir,\u00a0M., Tarjan, R.E.: Linear-time algorithms for visibility and shortest path problems inside triangulated simple polygons. Algorithmica 2, 209\u2013233 (1987)","journal-title":"Algorithmica"},{"key":"9551_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/978-3-642-02882-3_25","volume-title":"Proc. Conference on Combinatorics and Computing","author":"C. Gutwenger","year":"2009","unstructured":"Gutwenger,\u00a0C., Mutzel,\u00a0P., Zey,\u00a0B.: On the hardness and approximability of planar biconnectivity augmentation. In: Proc. Conference on Combinatorics and Computing. Lecture Notes in Computer Science, vol.\u00a05609, pp.\u00a0249\u2013257. Springer, Berlin (2009)"},{"key":"9551_CR14","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1007\/BF01994880","volume":"32","author":"J. Hershberger","year":"1992","unstructured":"Hershberger,\u00a0J., Suri,\u00a0S.: Applications of a semi-dynamic convex hull algorithm. BIT Numer. Math. 32, 249\u2013267 (1992)","journal-title":"BIT Numer. Math."},{"issue":"5","key":"9551_CR15","doi-asserted-by":"crossref","first-page":"889","DOI":"10.1137\/0222056","volume":"22","author":"T.-S. Hsu","year":"1993","unstructured":"Hsu, T.-S., Ramachandran,\u00a0V.: On finding a minimum augmentation to biconnect a graph. SIAM J. Comput. 22(5), 889\u2013912 (1993)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"9551_CR16","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1016\/S0196-6774(02)00223-7","volume":"45","author":"T.-S. Hsu","year":"2002","unstructured":"Hsu, T.-S.: Simpler and faster biconnectivity augmentation. J. Algorithms 45(1), 55\u201371 (2002)","journal-title":"J. Algorithms"},{"key":"9551_CR17","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1016\/j.jctb.2004.01.004","volume":"94","author":"B. Jackson","year":"2005","unstructured":"Jackson,\u00a0B., Jord\u00e1n,\u00a0T.: Independence free graphs and vertex connectivity augmentation. J. Comb. Theory, Ser. B 94, 31\u201377 (2005)","journal-title":"J. Comb. Theory, Ser. B"},{"key":"9551_CR18","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1006\/jagm.1996.0034","volume":"21","author":"G. Kant","year":"1996","unstructured":"Kant,\u00a0G.: Augmenting outerplanar graphs. J. Algorithms 21, 1\u201325 (1996)","journal-title":"J. Algorithms"},{"key":"9551_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"286","DOI":"10.1007\/BFb0028270","volume-title":"Proceedings of the 2nd Workshop on Algorithms and Data Structures","author":"G. Kant","year":"1991","unstructured":"Kant,\u00a0G., Bodlaender, H.L.: Planar graph augmentation problems. In: Proceedings of the 2nd Workshop on Algorithms and Data Structures. Lecture Notes in Computer Science, vol.\u00a0519, pp.\u00a0286\u2013298. Springer, Berlin (1991)"},{"key":"9551_CR20","volume-title":"Handbook of Approximation Algorithms and Metaheuristics","author":"G. Kortsarz","year":"2007","unstructured":"Kortsarz,\u00a0G., Nutov,\u00a0Z.: Approximating minimum cost connectivity problems. In: Gonzalez, T.F. (ed.) Handbook of Approximation Algorithms and Metaheuristics. CRC Press, Boca Raton (2007) (Chap.\u00a058)"},{"key":"9551_CR21","volume-title":"Combinatorial Problems and Exercises","author":"L. Lov\u00e1sz","year":"1979","unstructured":"Lov\u00e1sz,\u00a0L.: Combinatorial Problems and Exercises. North-Holland, Amsterdam (1979)"},{"key":"9551_CR22","doi-asserted-by":"crossref","first-page":"145","DOI":"10.1016\/S0167-5060(08)70504-1","volume":"3","author":"W. Mader","year":"1978","unstructured":"Mader,\u00a0W.: A\u00a0reduction method for edge-connectivity in graphs. Ann. Discrete Math. 3, 145\u2013164 (1978)","journal-title":"Ann. Discrete Math."},{"issue":"5","key":"9551_CR23","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1016\/0020-0190(79)90069-3","volume":"9","author":"D. McCallum","year":"1979","unstructured":"McCallum,\u00a0D., Avis,\u00a0D.: A\u00a0linear algorithm for finding the convex hull of a simple polygon. Inf. Process. Lett. 9(5), 201 (1979)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"9551_CR24","doi-asserted-by":"crossref","first-page":"137","DOI":"10.1023\/A:1024470929537","volume":"7","author":"H. Nagamochi","year":"2003","unstructured":"Nagamochi,\u00a0H., Eades,\u00a0P.: An edge-splitting algorithm in planar graphs. J. Comb. Optim. 7(2), 137\u2013159 (2003)","journal-title":"J. Comb. Optim."},{"key":"9551_CR25","doi-asserted-by":"crossref","first-page":"253","DOI":"10.1006\/jagm.1998.0983","volume":"30","author":"H. Nagamochi","year":"1999","unstructured":"Nagamochi,\u00a0H., Ibaraki,\u00a0T.: Augmenting edge-connectivity over the entire range in $\\tilde {O}(nm)$ time. J. Algorithms 30, 253\u2013301 (1999)","journal-title":"J. Algorithms"},{"key":"9551_CR26","doi-asserted-by":"crossref","first-page":"447","DOI":"10.1016\/S0166-218X(01)00349-3","volume":"123","author":"H. Nagamochi","year":"2002","unstructured":"Nagamochi,\u00a0H., Ibaraki,\u00a0T.: Graph connectivity and its augmentation: applications of MA orderings. Discrete Appl. Math. 123, 447\u2013472 (2002)","journal-title":"Discrete Appl. Math."},{"issue":"6","key":"9551_CR27","doi-asserted-by":"crossref","first-page":"668","DOI":"10.1007\/BF01224737","volume":"27","author":"J. Plesn\u00edk","year":"1976","unstructured":"Plesn\u00edk,\u00a0J.: Minimum block containing a given graph. Arch. Math. 27(6), 668\u2013672 (1976)","journal-title":"Arch. Math."},{"key":"9551_CR28","doi-asserted-by":"crossref","first-page":"329","DOI":"10.1016\/0012-365X(93)90376-5","volume":"114","author":"J.A. Poutr\u00e9 La","year":"1993","unstructured":"La Poutr\u00e9, J.A., van Leeuwen,\u00a0J., Overmars, M.H.: Maintenance of 2- and 3-edge-connected components of graphs\u00a0I. Discrete Math. 114, 329\u2013359 (1993)","journal-title":"Discrete Math."},{"key":"9551_CR29","doi-asserted-by":"crossref","first-page":"1521","DOI":"10.1137\/S0097539793257770","volume":"29","author":"J.A. Poutr\u00e9 La","year":"2000","unstructured":"La Poutr\u00e9, J.A.: Maintenance of 2- and 3-edge-connected components of graphs\u00a0II. SIAM J. Comput. 29, 1521\u20131549 (2000)","journal-title":"SIAM J. Comput."},{"key":"9551_CR30","series-title":"Texts and Monographs in Computer Science","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry: An Introduction","author":"F.P. Preparata","year":"1985","unstructured":"Preparata, F.P., Shamos, M.I.: Computational Geometry: An Introduction. Texts and Monographs in Computer Science. Springer, Berlin (1985)"},{"key":"9551_CR31","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1137\/0206003","volume":"6","author":"A. Rosenthal","year":"1977","unstructured":"Rosenthal,\u00a0A., Goldner,\u00a0A.: Smallest augmentations to biconnect a graph. SIAM J. Comput. 6, 55\u201366 (1977)","journal-title":"SIAM J. Comput."},{"key":"9551_CR32","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1016\/j.endm.2008.06.009","volume":"31","author":"I. Rutter","year":"2008","unstructured":"Rutter,\u00a0I., Wolff,\u00a0A.: Augmenting the connectivity of planar and geometric graphs. Electron. Notes Discrete Math. 31, 53\u201356 (2008)","journal-title":"Electron. Notes Discrete Math."},{"issue":"5","key":"9551_CR33","doi-asserted-by":"crossref","first-page":"388","DOI":"10.1016\/j.comgeo.2008.06.005","volume":"42","author":"D.L. Souvaine","year":"2009","unstructured":"Souvaine, D.L., T\u00f3th, C.D.: A\u00a0vertex-face assignment for plane graphs. Comput. Geom. Theory Appl. 42(5), 388\u2013394 (2009)","journal-title":"Comput. Geom. Theory Appl."},{"key":"9551_CR34","unstructured":"T\u00f3th, C.D.: Connectivity augmentation in planar straight line graphs. Eur. J. Comb. (2010, to appear). http:\/\/math.ucalgary.ca\/~cdtoth\/2edgecon20.pdf"},{"key":"9551_CR35","doi-asserted-by":"crossref","DOI":"10.3138\/9781487584863","volume-title":"Connectivity in Graphs","author":"W.T. Tutte","year":"1966","unstructured":"Tutte, W.T.: Connectivity in Graphs. University of Toronto Press, Toronto (1966)"},{"key":"9551_CR36","first-page":"563","volume-title":"Proceedings of the 42nd Symposium on Theory of Computing","author":"L. V\u00e9gh","year":"2010","unstructured":"V\u00e9gh,\u00a0L.: Augmenting undirected node-connectivity by one. In: Proceedings of the 42nd Symposium on Theory of Computing, pp. 563\u2013572. ACM Press, New York (2010)"},{"issue":"1","key":"9551_CR37","doi-asserted-by":"crossref","first-page":"96","DOI":"10.1016\/0022-0000(87)90038-9","volume":"35","author":"T. Watanabe","year":"1987","unstructured":"Watanabe,\u00a0T., Nakamura,\u00a0A.: Edge-connectivity augmentation problems. J. Comput. Syst. Sci. 35(1), 96\u2013144 (1987)","journal-title":"J. Comput. Syst. Sci."}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9551-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00453-011-9551-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00453-011-9551-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,6,21]],"date-time":"2020-06-21T23:37:57Z","timestamp":1592782677000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00453-011-9551-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,8,3]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["9551"],"URL":"https:\/\/doi.org\/10.1007\/s00453-011-9551-0","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,8,3]]}}}