Title: Geometric Biplane Graphs I: Maximal Graphs,
Abstract: We study biplane graphs drawn on a finite planar point set $S$ in general
position. This is the family of geometric graphs whose vertex set is $S$ and
can be decomposed into two plane graphs. We show that two maximal biplane
graphs---in the sense that no edge can be added while staying biplane---may
differ in the number of edges, and we provide an efficient algorithm for adding
edges to a biplane graph to make it maximal. We also study extremal properties
of maximal biplane graphs such as the maximum number of edges and the largest
maximum connectivity over $n$-element point sets.