Graphs drawn with few crossings per edge (Q1272189)

From MaRDI portal
Revision as of 02:45, 5 March 2024 by Import240304020342 (talk | contribs) (Set profile property.)
scientific article
Language Label Description Also known as
English
Graphs drawn with few crossings per edge
scientific article

    Statements

    Graphs drawn with few crossings per edge (English)
    0 references
    0 references
    0 references
    24 November 1998
    0 references
    If a graph with \(v\) vertices and \(e\) edges can be drawn on the plane so that every edge crosses at most \(k\) others, then \(e\leq (k+3)(v-2)4\) for \(k\leq 4\) and \(e\leq 4.108 \sqrt{k}v\) in general. For the crossing number \(c\) (the minimal number of edge crossings over all planar drawings) the estimate \(c> 0.029 e^3/v^2 - 0.9 v \) is proved. This can be used to improve the constants in the Szemerédi-Trotter theorem.
    0 references
    graphs drawn on plane
    0 references
    crossing number
    0 references

    Identifiers