On the maximum number of edges in quasi-planar graphs
type: Item
instance of: scholarly article
title: On the maximum number of edges in quasi-planar graphs
zbMATH Open document ID: 1120.05045
author: Eyal Ackerman
author: Gábor Tardos
published in: Journal of Combinatorial Theory. Series A
publication date: 2007-05-04T00:00:00Z
review text: The paper improves on the known result that graphs which can be properly drawn in the plane so that there are no three pairwise crossing edges (quasiplanar graphs) have a linear number of edges in relation to the number of vertices by proving that such a graph has no more than \(8| V| -20\) edges for \(| V| \geq 3\). The authors show that for each positive integer \(n\) there is a quasiplanar graph with \(| V| =n\) and \(7n-O(1)\) edges. They also give an exceedingly simple and gemlike proof of the linearity of the number of edges, and consider some relaxations and restrictions of quasiplanarity for which they are able to close the gap between the upper bounds and the lower bounds given by construction.
reviewed by: Adrian Riskin
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 05C10
zbMATH DE Number: 5149438
zbMATH Keywords: Turán-type problems
zbMATH Keywords: geometric graphs
zbMATH Keywords: quasiplanar graphs
zbMATH Keywords: topological graphs
zbMATH Keywords: discharging method
MaRDI profile type: Publication
full work available at URL: j.jcta.2006.08.002
OpenAlex ID: W1967421215
cites work: Q3601547
cites work: Quasi-planar graphs have a linear number of edges
cites work: Every planar map is four colorable. I: Discharging
cites work: A Turán-type theorem on chords of a convex polygon
cites work: Q4011323
cites work: Topological graphs with no large grids
cites work: Discrete and Computational Geometry
cites work: Q4657589
cites work: Graphs drawn with few crossings per edge
cites work: Construction of Locally Plane Graphs with Many Edges
cites work: Crossing Stars in Topological Graphs
DOI: 10.1016/J.JCTA.2006.08.002
description: scientific article; zbMATH DE number 5149438