Augmenting the edge connectivity of planar straight line graphs to three

• Csaba D. Tóth ^[1] ; Pavel Valtr ^[2]
  1. [1] University of Calgary

     University of Calgary

     Canadá

     
  2. [2] Charles University in Prague

     Charles University in Prague

     Chequia

     
• Localización: XIII Encuentros de Geometría Computacional: Zaragoza, del 29 de junio al 1 de julio de 2009 / Alfredo García Olaverri (ed. lit.) , Javier Tejel Altarriba (ed. lit.) , 2009, ISBN 978-84-92774-11-1, págs. 157-162
• Idioma: español
• Texto completo no disponible (Saber más ...)
• Resumen

  • We characterize the 2-connected and 2-edge connected planar straight line graphs, respectively, that have embedding preserving augmentations to 3-connected and 3-edge connected planar straight line graphs. If such an augmentation is possible, then it can be done using at most n − 2 new edges in the worst case. These bounds are best possible.