Topological Graphs with No Large Grids |
| |
Authors: | János Pach Rom Pinchasi Micha Sharir Géza Tóth |
| |
Institution: | (1) City College, CUNY and Courant Institute of Mathematical Sciences, New York University, New York, NY 10012, USA;(2) Department of Mathematics, Massachusetts Institute of Technology, Cambridge, MA 02139, USA;(3) School of Computer Science, Tel Aviv University, Tel Aviv, 69 978, Israel;(4) Courant Institute of Mathematiscal Sciences, New York University, New York, NY 10012, USA;(5) Rényi Institute, Hungarian Academy of Sciences, Budapest, Hungary |
| |
Abstract: | 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. |
| |
Keywords: | Topological graphs Crossing edges |
本文献已被 SpringerLink 等数据库收录! |
|