Degenerate Crossing Numbers |
| |
Authors: | János Pach Géza Tóth |
| |
Institution: | (1) Rényi Institute, Hungarian Academy of Sciences, Budapest, Hungary;(2) EPFL, Lausanne, Switzerland |
| |
Abstract: | Let G be a graph with n vertices and e≥4n edges, drawn in the plane in such a way that if two or more edges (arcs) share an interior point p, then they properly cross one another at p. It is shown that the number of crossing points, counted without multiplicity, is at least constant times e and that the order of magnitude of this bound cannot be improved. If, in addition, two edges are allowed to cross only at
most once, then the number of crossing points must exceed constant times (e/n)4.
The research of J. Pach was supported by NSF grant CCF-05-14079 and by grants from NSA, PSC-CUNY, BSF, and OTKA-K-60427.
The research of G. Tóth was supported by OTKA-K-60427. |
| |
Keywords: | Crossing number Crossing lemma Bisection width Euler characteristics Incidences Multiple crossings |
本文献已被 SpringerLink 等数据库收录! |
|