TY - CONF
AU - Garcia, A.
AU - Hurtado, F.
AU - Korman, M.
AU - Matos, I. P.
AU - Saumell, M.
AU - Silveira, R.
AU - Tejel, F.
AU - Tóth, C.D.
T3 - Mexican Conference on Discrete Mathematics and Computational Geometry 2013
PY - 2013
Y1 - 2013
SP - 223
EP - 234
UR - http://hdl.handle.net/2117/26085
AB - We study biplane graphs drawn on a nite point set S in the plane in general position. This is the family of geometric graphs whose vertex set is S and can be decomposed into two plane graphs. It is shown that every suciently large set S admits a 5-connected biplane graph; and there are arbitrarily large point sets that do not admit any 6-connected biplane graph. Every plane graph other than the wheel can be augmented into a 4-connected biplane graph; and there are arbitrarily large plane graphs that cannot be augmented to a 5-connected biplane graph. In a companion paper we study extremal properties of biplane graphs such as the maximal number of edges and the largest minimum degree of biplane graphs over n -element point sets
AB - We study biplane graphs drawn on a nite 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 su ciently 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.
T2 - Mexican Conference on Discrete Mathematics and Computational Geometry
TI - Geometric Biplane Graphs II: Graph Augmentation
ER -