On edges crossing few other edges in simple topological complete graphs

Abstract

Let $h=h(n)$ be the smallest integer such that every simple topological complete graph on $n$ vertices contains an edge crossing at most $h$ other edges. We show that $\Omega(n^{3/2})\le h(n) \le O(n^2/\log^{1/4}n)$.

We also show that the analogous function on other surfaces (torus, Klein bottle) grows as $cn^2$.

Keywords

• edges
• crossing
• other
• edges
• simple
• topological
• complete
• graphs