Augmenting the Edge Connectivity of Planar Straight Line Graphs to Three

被引:6
作者
Al-Jubeh, Marwan [2 ]
Ishaque, Mashhood [2 ]
Redei, Kristof [2 ]
Souvaine, Diane L. [2 ]
Toth, Csaba D. [1 ]
Valtr, Pavel [3 ,4 ]
机构
[1] Univ Calgary, Dept Math, Calgary, AB T2N 1N4, Canada
[2] Tufts Univ, Dept Comp Sci, Medford, MA 02155 USA
[3] Charles Univ Prague, Dept Appl Math, CR-11800 Prague, Czech Republic
[4] Charles Univ Prague, Inst Theoret Comp Sci, CR-11800 Prague, Czech Republic
基金
加拿大自然科学与工程研究理事会; 美国国家科学基金会;
关键词
Connectivity augmentation; Planar straight line graph; Graph embedding; 3-EDGE-CONNECTED COMPONENTS; CONVEX-HULL; AUGMENTATION; BICONNECT; ALGORITHM;
D O I
10.1007/s00453-011-9551-0
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
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.
引用
收藏
页码:971 / 999
页数:29
相关论文
共 37 条
  • [1] Augmenting the connectivity of geometric graphs
    Abellanas, M.
    Garcia, A.
    Hurtado, F.
    Tejel, J.
    Urrutia, J.
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2008, 40 (03): : 220 - 230
  • [2] ON THE CONVEX LAYERS OF A PLANAR SET
    CHAZELLE, B
    [J]. IEEE TRANSACTIONS ON INFORMATION THEORY, 1985, 31 (04) : 509 - 517
  • [3] Successive edge-connectivity augmentation problems
    Cheng, E
    Jordán, T
    [J]. MATHEMATICAL PROGRAMMING, 1999, 84 (03) : 577 - 593
  • [4] Eswaran K. P., 1976, SIAM Journal on Computing, V5, P653, DOI 10.1137/0205044
  • [5] Fialko S., 1998, Proceedings of the Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, ser. SODA '98, P260
  • [6] AUGMENTING GRAPHS TO MEET EDGE-CONNECTIVITY REQUIREMENTS
    FRANK, A
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (01) : 25 - 53
  • [7] MAINTAINING THE 3-EDGE-CONNECTED COMPONENTS OF A GRAPH ONLINE
    GALIL, Z
    ITALIANO, GF
    [J]. SIAM JOURNAL ON COMPUTING, 1993, 22 (01) : 11 - 28
  • [8] Augmenting the Connectivity of Outerplanar Graphs
    Garcia, A.
    Hurtado, F.
    Noy, M.
    Tejel, J.
    [J]. ALGORITHMICA, 2010, 56 (02) : 160 - 179
  • [9] On triconnected and cubic plane graphs on given point sets
    Garcia, Alfredo
    Hurtado, Ferran
    Huemer, Clemens
    Tejel, Javier
    Valtr, Pavel
    [J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2009, 42 (09): : 913 - 922
  • [10] Dynamic ray shooting and shortest paths in planar subdivisions via balanced geodesic triangulations
    Goodrich, MT
    Tamassia, R
    [J]. JOURNAL OF ALGORITHMS, 1997, 23 (01) : 51 - 73