On edges crossing few other edges in simple topological complete graphs (Q1011770): Difference between revisions

A simple topological graph is a representation in the plane of a graph such that the vertices of the graph correspond to distinct points in the plane and the edges correspond to Jordan curves connecting the corresponding points and having at most one point in common, either a vertex-point or a crossing. Now 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. The authors show that \(\Omega(n^{3/2}) \leq h(n) \leq O(n^2/\log^{1/4} n)\). They also show that the analogous function on the torus and the Klein bottle grows as \(cn^2\).