Geometric Biplane Graphs I: Maximal Graphs

We study biplane graphs drawn on a finite planar point set $$S$$S in general position. This is the family of geometric graphs whose vertex set is $$S$$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$$n-element point sets.