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

preprint2016arXivOpen access

Abstract

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

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.