Journal of Combinatorics

Volume 1 (2010)

Number 3

Disjoint edges in topological graphs

DOI: http://dx.doi.org/10.4310/JOC.2010.v1.n3.a4

Authors

János Pach (City College, New York)

Géza Tóth (Rényi Institute, Hungarian Academy of Sciences, Budapest, Hungary)

Abstract

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)