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

来源：

ALGORITHMICA | 2011年 / 61卷 / 04期

基金：

加拿大自然科学与工程研究理事会; 美国国家科学基金会;

关键词：

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 条

[31] Rosenthal A., 1977, SIAM Journal on Computing, V6, P55, DOI 10.1137/0206003
[32] Rutter I., 2008, ELECT NOTES DISCRETE, V31, P53, DOI [10.1016/j.endm.2008.06.009, DOI 10.1016/J.ENDM.2008.06.009]
[33] A vertex-face assignment for plane graphs
Souvaine, Diane L.
Toth, Csaba D.
[J]. COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2009, 42 (05): : 388 - 394
[34] TOTH CD, 2010, EUR J COMB IN PRESS
[35] Tutte W. T., 1966, CONNECTIVITY GRAPHS
[36] Végh LA, 2010, ACM S THEORY COMPUT, P563
[37] EDGE-CONNECTIVITY AUGMENTATION PROBLEMS
WATANABE, T
NAKAMURA, A
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1987, 35 (01) : 96 - 144

← 1 2 3 4 →