Abstract
A topological graph is -quasi-planar if it does not contain pairwise crossing edges. A 20-year-old conjecture asserts that for every fixed , the maximum number of edges in a -quasi-planar graph on vertices is . Fox and Pach showed that every -quasi-planar graph with vertices has at most edges. We improve this upper bound to , where denotes the inverse Ackermann function and depends only on , for -quasi-planar graphs in which any two edges intersect in a bounded number of points. We also show that every -quasi-planar graph with vertices in which any two edges have at most one point in common has at most edges. This improves the previously known upper bound of obtained by Fox, Pach, and Suk.
Connections
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 review
No reviews yet.
Discussion 0
Add a comment
No comments yet.