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

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(\log n{)}^{O(\log k)}$ edges. We improve this upper bound to $2^{\alpha (n{)}^c}n\log n$, where $\alpha (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(n\log n)$ edges. This improves the previously known upper bound of $2^{\alpha (n{)}^c}n\log n$ obtained by Fox, Pach, and Suk.

Final version, minor corrections

References in corpus (1)

• Coloring intersection graphs of arc-connected sets in the plane

Cited by in corpus (9)

• An annotated bibliography on 1-planarity
• A Survey on Graph Drawing Beyond Planarity
• Simple $k$-Planar Graphs are Simple $(k+1)$-Quasiplanar
• On-line approach to off-line coloring problems on graphs with geometric representations
• Triangle-Free Penny Graphs: Degeneracy, Choosability, and Edge Count
• Sequences of formation width $4$ and alternation length $5$
• Bounding sequence extremal functions with formations
• On the zone of a circle in an arrangement of lines
• Covering nearly surface-embedded graphs with a fixed number of balls