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)) {= h(n) {= 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