Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Journal articles
  4. Degenerate crossing numbers
 
research article

Degenerate crossing numbers

Pach, János  
•
Tóth, Géza
2009
Discrete and Computational Geometry

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).

  • Files
  • Details
  • Metrics
Loading...
Thumbnail Image
Name

454_2009_Article_9141.pdf

Type

Publisher's Version

Version

http://purl.org/coar/version/c_970fb48d4fbd8a85

Access type

openaccess

Size

255.87 KB

Format

Adobe PDF

Checksum (MD5)

8c0461dfc4b4c34f46183050b5a1d801

Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés