Geometric Biplane Graphs II: Graph Augmentation

被引：3

作者：

Garcia, Alfredo ^{[1
]}

Hurtado, Ferran ^{[2
]}

Korman, Matias ^{[3
]}

Matos, Ines ^{[4
,5
]}

Saumell, Maria ^{[6
,7
]}

Silveira, Rodrigo I. ^{[2
]}

Tejel, Javier ^{[1
]}

Toth, Csaba D. ^{[8
]}

机构：

[1] Univ Zaragoza, IUMA, Dept Metodos Estadist, Zaragoza, Spain

[2] UPC, Dept Matemat Aplicada 2, Barcelona, Spain

[3] NII, Erato Kawarabayashi Large Graph Project, JST, Tokyo, Japan

[4] Univ Aveiro, Dept Matemat, P-3800 Aveiro, Portugal

[5] Univ Aveiro, CIDMA, P-3800 Aveiro, Portugal

[6] Univ W Bohemia, Dept Math, Plzen, Czech Republic

[7] Univ W Bohemia, European Ctr Excellence NTIS New Technol Informat, Plzen, Czech Republic

[8] Calif State Univ Northridge, Dept Math, Los Angeles, CA USA

来源：

GRAPHS AND COMBINATORICS | 2015年 / 31卷 / 02期

基金：

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

关键词：

Geometric graphs; Biplane graphs; k-connected graphs; Graph augmentation; CONNECTIVITY;

D O I：

10.1007/s00373-015-1547-0

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

We study biplane graphs drawn on a finite point set in the plane in general position. This is the family of geometric graphs whose vertex set is and which can be decomposed into two plane graphs. We show that every sufficiently large point set admits a 5-connected biplane graph and that there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Furthermore, we show that every plane graph (other than a wheel or a fan) can be augmented into a 4-connected biplane graph. However, there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph by adding pairwise noncrossing edges.

引用

页码：427 / 452

页数：26

共 29 条

[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] Al-Jubeh M., 2013, 30 ESSAYS GEOMETRIC, P49
[3] 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
[J]. ALGORITHMICA, 2011, 61 (04) : 971 - 999
[4] [Anonymous], P MEX C DISCR MATH C
[5] Barnette D., 1974, Discrete Mathematics, V7, P199, DOI 10.1016/0012-365X(74)90035-1
[6] The LCA problem revisited
Bender, MA
Farach-Colton, M
[J]. LATIN 2000: THEORETICAL INFORMATICS, 2000, 1776 : 88 - 94
[7] BOOK THICKNESS OF A GRAPH
BERNHART, F
KAINEN, PC
[J]. JOURNAL OF COMBINATORIAL THEORY SERIES B, 1979, 27 (03) : 320 - 331
[8] Construction of planar triangulations with minimum degree 5
Brinkmann, G
McKay, BD
[J]. DISCRETE MATHEMATICS, 2005, 301 (2-3) : 147 - 163
[9] GENERATION PROCEDURE FOR SIMPLE 3-POLYTOPES WITH CYCLICALLY 5-CONNECTED GRAPHS
BUTLER, JW
[J]. CANADIAN JOURNAL OF MATHEMATICS-JOURNAL CANADIEN DE MATHEMATIQUES, 1974, 26 (03): : 686 - 708
[10] Chvatal V., 1985, TRAVELING SALESMAN P, P403

← 1 2 3 →