# zbMATH — the first resource for mathematics

Bounds for generalized thrackles. (English) Zbl 0959.05030
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.

##### MSC:
 05C10 Planar graphs; geometric and topological aspects of graph theory
##### Keywords:
graph drawing; thrackle; surface
Full Text: