Disjoint edges in topological graphs

A topological graph $G$ is a graph drawn in the plane so that its edgesare represented by Jordan arcs. $G$ is called simple, if anytwo edges have at most one point in common. It is shown that themaximum number of edges of a simple topological graph with $n$ verticesand no $k$ pairwise disjoint edges is $O(n\log^{5k-10}n)$. Theassumption that $G$ is simple cannot be dropped: for every $n$, thereexists a complete topological graph of $n$ vertices, whose any twoedges cross at most twice.

Full Text (PDF format)

Published 1 January 2010