Bounds for generalized thrackles
type: Item
instance of: scholarly article
title: Bounds for generalized thrackles
zbMATH Open document ID: 0959.05030
DOI: 10.1007/PL00009495
author: Yanyan Li
published in: Discrete \& Computational Geometry
publication date: 2001-04-20T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1422798
zbMATH Keywords: graph drawing
zbMATH Keywords: thrackle
zbMATH Keywords: surface
reviewed by: Jozef Širáň
MaRDI profile type: Publication
full work available at URL: pl00009495
OpenAlex ID: W2058825457
description: scientific article; zbMATH DE number 1422798