%0 Journal Article
%T Saturated simple and $k$-simple topological graphs
%A Jan Kyn£¿l
%A J¨¢nos Pach
%A Rado£¿ Radoi£¿i£¿
%A G¨¦za T¨®th
%J Mathematics
%D 2013
%I arXiv
%R 10.1016/j.comgeo.2014.10.008
%X 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.
%U http://arxiv.org/abs/1309.1046v2