Back to Search
Start Over
Geometric Biplane Graphs II: Graph Augmentation
- Source :
- Graphs and Combinatorics 31(2) (2015), 427-452
- Publication Year :
- 2017
-
Abstract
- We study biplane graphs drawn on a finite point set $S$ in the plane in general position. This is the family of geometric graphs whose vertex set is $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.
- Subjects :
- Computer Science - Computational Geometry
Subjects
Details
- Database :
- arXiv
- Journal :
- Graphs and Combinatorics 31(2) (2015), 427-452
- Publication Type :
- Report
- Accession number :
- edsarx.1702.01277
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1007/s00373-015-1547-0