research article
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).
Type
research article
Web of Science ID
WOS:000263976800003
Author(s)
Tóth, Géza
Date Issued
2009
Publisher
Published in
Volume
41
Issue
3
Start page
376
End page
384
Note
National Licences
Editorial or Peer reviewed
REVIEWED
Written at
EPFL
EPFL units
Available on Infoscience
November 26, 2010
Use this identifier to reference this record