Publication at Faculty of Mathematics and Physics |
2011
Abstract
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.