Saturated simple topological graphs
János Pach, Radoš Radoičić, Gézá Tóth · arXiv (Cornell University) · 2013
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. These constructions are nearly optimal: it is shown that every saturated simple topological graph with n vertices has at least cn edges for some constant c ≥ 1.5. Several related problems are also considered.