Degenerate crossing numbers

Let G be a graph with n vertices and ea parts per thousand yen4n 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).


Published in:
Discrete and Computational Geometry, 41, 3, 376-384
Year:
2009
Keywords:
Laboratories:




 Record created 2010-11-26, last modified 2018-09-13


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)