Elsevier

Computational Geometry

Volume 50, December 2015, Pages 24-33
Computational Geometry

New bounds on the maximum number of edges in k-quasi-planar graphs

https://doi.org/10.1016/j.comgeo.2015.06.001Get rights and content
Under an Elsevier user license
open archive

Abstract

A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A 20-year-old conjecture asserts that for every fixed k, the maximum number of edges in a k-quasi-planar graph on n vertices is O(n). Fox and Pach showed that every k-quasi-planar graph with n vertices has at most n(logn)O(logk) edges. We improve this upper bound to 2α(n)cnlogn, where α(n) denotes the inverse Ackermann function and c depends only on k, for k-quasi-planar graphs in which any two edges intersect in a bounded number of points. We also show that every k-quasi-planar graph with n vertices in which any two edges have at most one point in common has at most O(nlogn) edges. This improves the previously known upper bound of 2α(n)cnlogn obtained by Fox, Pach, and Suk.

Keywords

Topological graphs
k-Quasi-planar graphs
Turán-type problems

Cited by (0)

A preliminary version of this paper appeared in: Stephen Wismath, Alexander Wolff (Eds.), Graph Drawing, GD 2013, in: Lecture Notes Comput. Sci., vol. 8242, Springer, Berlin, 2013, pp. 95–106.

1

Andrew Suk is supported by NSF grant DMS-1500153.

2

Bartosz Walczak was supported by Swiss National Science Foundation grant 200020-144531 and by Ministry of Science and Higher Education of Poland grant 884/N-ESF-EuroGIGA/10/2011/0 within ESF EuroGIGA project GraDR.