Fox, J. and Pach, János and Suk, A. (2013) The number of edges in k-quasi-planar graphs. SIAM JOURNAL ON DISCRETE MATHEMATICS, 27 (1). pp. 550-561. ISSN 0895-4801
|
Text
1112.2361v1.pdf Available under License Creative Commons Attribution. Download (245kB) | Preview |
Abstract
A graph drawn in the plane is called k-quasi-planar if it does not contain k pairwise crossing edges. It has been conjectured for a long time that for every fixed k, the maximum number of edges of a k-quasi-planar graph with n vertices is O(n). The best known upper bound is n(log n) O(log k) . In the present note, we improve this bound to (n log n)2α ck (n) in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here α(n) denotes the (extremely slowly growing) inverse of the Ackermann function. We also make further progress on the conjecture for k-quasi-planar graphs in which every edge is drawn as an x-monotone curve. Extending some ideas of Valtr, we prove that the maximum number of edges of such graphs is at most 2ck6 n log n.
Item Type: | Article |
---|---|
Uncontrolled Keywords: | Graph theory; Upper Bound; Graphic methods; Crossing edges; Turán-type problems; Topological graphs; Quasi-planar graphs; Ackermann functions; |
Subjects: | Q Science / természettudomány > QA Mathematics / matematika |
SWORD Depositor: | MTMT SWORD |
Depositing User: | MTMT SWORD |
Date Deposited: | 13 Aug 2024 11:43 |
Last Modified: | 13 Aug 2024 11:43 |
URI: | https://real.mtak.hu/id/eprint/202519 |
Actions (login required)
![]() |
Edit Item |