Augmenting the connectivity of planar and geometric graphs

I. Rutter, A. Wolff

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

8 Citaten (Scopus)
1 Downloads (Pure)


In this paper we study some connectivity augmentation problems. We want to make planar graphs 2-vertex (or 2-edge) connected by adding edges such that the resulting graphs remain planar. We show that it is NP-hard to find a minimum-cardinality augmentation that makes a planar graph 2-edge connected. This was known for 2-vertex connectivity. We further show that both problems are hard in a geometric setting, even when restricted to trees. For the special case of convex geometric graphs we give efficient algorithms. We also study the following related problem. Given a plane geometric graph G, two vertices s and t of G, and an integer k, how many edges have to be added to G such that G contains k edge- (or vertex-) disjoint s-t paths? For k=2 we give optimal worst-case bounds; for k=3 we characterize all cases that have a solution.
Originele taal-2Engels
TitelProceedings International Conference on Topological and Geometric Graph Theory (TGGT'08, Paris, France, May 19-23, 2008)
RedacteurenP. Ossona de Mendez, M. Pocchiola, D. Poulalhon, J.L. Ramírez Alfonsín, G. Schaeffer
StatusGepubliceerd - 2008

Publicatie series

NaamElectronic Notes in Discrete Mathematics
ISSN van geprinte versie1571-0653


Duik in de onderzoeksthema's van 'Augmenting the connectivity of planar and geometric graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit