2011/06/06 by Andrew Suk, Suk, Andrew · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.CG #math.CO
paper · pdf · doi:10.48550/arxiv.1106.0958
arxiv created 2011/06/06 · openalex publication_date 2011/06/06 · arxiv updated 2015/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A topological graph is simple if every pair of its edges intersect at most once (either at a vertex or at their intersection). In 1996, Pach, Shahrokhi, and Szegedy \citepach showed that every n-vertex simple k-quasi-planar graph contains at most O(n(log n)2k-4) edges. This upper bound was recently improved (for large k) by Fox and Pach \citefox to n(log n)O(log k). In this note, we show that all such graphs contain at most (nlog2n)2^αck(n) edges, where α(n) denotes the inverse Ackermann function and ck is a constant that depends only on k.