Abstract | ||
---|---|---|
We study biplane graphs drawn on a finite point set $$S$$S in the plane in general position. This is the family of geometric graphs whose vertex set is $$S$$S 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. |
Year | DOI | Venue |
---|---|---|
2017 | 10.1007/s00373-015-1547-0 | Graphs and Combinatorics |
Keywords | DocType | Volume |
Geometric graphs, Biplane graphs, $$k$$k-connected graphs, Graph augmentation | Journal | 31 |
Issue | ISSN | Citations |
2 | 1435-5914 | 1 |
PageRank | References | Authors |
0.36 | 14 | 8 |
Name | Order | Citations | PageRank |
---|---|---|---|
Alfredo García | 1 | 70 | 6.48 |
Ferran Hurtado | 2 | 744 | 86.37 |
Matias Korman | 3 | 178 | 37.28 |
Inês Matos | 4 | 16 | 5.10 |
Maria Saumell | 5 | 58 | 10.50 |
Rodrigo I. Silveira | 6 | 141 | 28.68 |
Javier Tejel | 7 | 90 | 13.60 |
Csaba D. Tóth | 8 | 573 | 70.13 |