Graphs drawn with few crossings per edge
type: Item
instance of: scholarly article
title: Graphs drawn with few crossings per edge
zbMATH Open document ID: 0902.05017
DOI: 10.1007/BF01215922
author: János Pach
author: Géza Tóth
published in: Combinatorica
publication date: 1998-11-24T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 1226449
zbMATH Keywords: graphs drawn on plane
zbMATH Keywords: crossing number
reviewed by: Péter Komjáth
MaRDI profile type: Publication
Wikidata QID: Q56001341
cites work: Crossing-Free Subgraphs
cites work: Combinatorial complexity bounds for arrangements of curves and spheres
cites work: Q5831393
cites work: On the Number of Incidences Between Points and Curves
cites work: Extremal problems in discrete geometry
full work available at URL: https://doi.org/10.1007/bf01215922
OpenAlex ID: W1723997437
DBLP publication ID: journals/combinatorica/PachT97
description: scientific article; zbMATH DE number 1226449