Saturated simple and $k$-simple topological graphs

Abstract

A simple topological graph $G$ is a graph drawn in the plane so that any pair of edges have at most one point in common, which is either an endpoint or a proper crossing. $G$ is called saturated if no further edge can be added without violating this condition. We construct saturated simple topological graphs with $n$ vertices and $O(n)$ edges. For every $k>1$, we give similar constructions for $k$-simple topological graphs, that is, for graphs drawn in the plane so that any two edges have at most $k$ points in common. We show that in any $k$-simple topological graph, any two independent vertices can be connected by a curve that crosses each of the original edges at most $2k$ times. Another construction shows that the bound $2k$ cannot be improved. Several other related problems are also considered.

25 pages, 17 figures, added some new results and improvements

References in corpus (1)

• Improved enumeration of simple topological graphs

Cited by in corpus (2)

• Saturated $k$-Plane Drawings with Few Edges
• Saturated simple and 2-simple topological graphs with few edges