Bounds for generalized thrackles (Q1971504)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Bounds for generalized thrackles
scientific article

    Statements

    Bounds for generalized thrackles (English)
    0 references
    0 references
    0 references
    20 April 2001
    0 references
    A thrackle (or a generalized thrackle) is a drawing of a graph in which each pair of edges meet precisely once (or an odd number of times, respectively). For a graph with \(n\) vertices and \(m\) edges it is shown that \(m\leq 3(n-1)/2\) for thrackles in a plane, while \(m\leq 2n-2\) for generalized thrackles in a plane; this improves known results by Lovász, Pach and Szegedy. The paper also examines thrackles on closed surfaces, with the following main result: A bipartite graph can be drawn as a generalized thrackle on a closed connected orientable surface if and only if the graph can be embedded in that surface.
    0 references
    0 references
    graph drawing
    0 references
    thrackle
    0 references
    surface
    0 references
    0 references