Fulltext

Degenerate Crossing Numbers

Pach, János ; Tóth, Géza

In: Discrete & Computational Geometry, 2009, vol. 41, no. 3, p. 376-384

Ajouter à la liste personnelle
    Titre
    • Degenerate Crossing Numbers
    Auteur
    • Pach, János. Rényi Institute, Hungarian Academy of Sciences, Budapest, Hungary
    • Tóth, Géza. Rényi Institute, Hungarian Academy of Sciences, Budapest, Hungary
    Type de document
    • Postprint
    Langue
    • Anglais
    Publié dans
    • Discrete & Computational Geometry, 2009, vol. 41, no. 3, p. 376-384. Springer-Verlag
    Autre version électronique
    Identifiant OAI-PMH
    • oai:doc.rero.ch:320297
    Summary
    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 timese 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