Topological Graphs with No Large Grids

Let G be a topological graph with n vertices, i.e., a graph drawn in the plane with edges drawn as simple Jordan curves. It is shown that, for any constants k,l, there exists another constant C(k,l), such that if G has at least C(k,l)n edges, then it contains a k×l-gridlike configuration, that is, it contains k+l edges such that each of the first k edges crosses each of the last l edges. Moreover, one can require the first k edges to be incident to the same vertex. Received: April, 2003 Janos Pach and Micha Sharir has been supported by NSF Grants CCR-97-32101 and CCR-00-98246, and by a joint grant from the U.S.–Israel Binational Science Foundation. János Pach has also been supported by PSC-CUNY Research Award 63382-0032 and by OTKA T-032452. Micha Sharir has also been supported by a grant from the Israeli Academy of Sciences for a Center of Excellence in Geometric Computing at Tel Aviv University, and by the Hermann Minkowski–MINERVA Center for Geometry at Tel Aviv University. Géza Tóth has been supported by OTKA-T-038397 and by an award from the New York University Research Challenge Fund.