Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three

作者：Al Jubeh Marwan; Ishaque Mashhood; Redei Kristof; Souvaine Diane L; Toth Csaba D^*; Valtr Pavel

来源：Algorithmica, 2011, 61(4): 971-999.

DOI：10.1007/s00453-011-9551-0

• Connectivity augmentation
• Planar straight line graph
• Graph embedding

We characterize the planar straight line graphs (Pslgs) that can be augmented to 3-connected and 3-edge-connected Pslgs, respectively. We show that if a Pslg with n vertices can be augmented to a 3-edge-connected Pslg, then at most 2n-2 new edges are always sufficient and sometimes necessary for the augmentation. If the input Pslg is, in addition, already 2-edge-connected, then n-2 new edges are always sufficient and sometimes necessary for the augmentation to a 3-edge-connected Pslg.

• 出版日期2011-12