Geometric Biplane Graphs II: Graph Augmentation
2015
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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
30
References
7
Citations
NaN
KQI