Description
Abstract: A topological graph is a graph drawn in the plane such that its vertices are represented by points, and its edges are represented by non-self-intersecting curves connecting the corresponding points. A topological graph is simple if any two of its edges intersect at most once, either at a common endpoint or at a proper crossing point. A k-face generated by a topological graph is the open bounded region enclosed by the edges of a non-self-intersecting k-cycle.
We prove that every n-vertex complete simple topological graph generates at least \Omega(n) pairwise disjoint 4-faces. This improves upon a recent result by Hubard and Suk. As an immediate corollary, every n-vertex complete simple topological graph drawn in the unit square generates a 4-face with area at most O(1/n). This can be seen as a topological variant of Heilbronn's problem for 4-faces. We construct examples showing that our result is asymptotically tight. We also discuss the similar problem for k-faces with arbitrary k>=3.