Crossing numbers of beyond-planar graphs (Q5918404)

From MaRDI portal
scientific article; zbMATH DE number 7437222
Language Label Description Also known as
English
Crossing numbers of beyond-planar graphs
scientific article; zbMATH DE number 7437222

    Statements

    Crossing numbers of beyond-planar graphs (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    1 December 2021
    0 references
    The article is devoted to further study the question of the best planar realization of a graph, including the one with the minimum possible number of edge intersections. Particular attention is paid to the study of three families of graphs, namely, \(k\)-planar, fan-planar and \(k\)-quasi-planar graphs. The authors prove ``that there are \(n\)-vertex 1-planar (quasi-planar, fan-planar) graphs such that any \(1\)-planar (quasi-planar, fan-planar) drawing has \(\Omega(n)\) crossings, while \(\mathcal{O}(1)\) crossings suffice in a crossing-minimal drawing without restrictions on local edge crossing patterns.''
    0 references
    crossing numbers
    0 references
    beyond planarity
    0 references
    1-planar graph
    0 references

    Identifiers