The number of edges in k-quasi-planar graphs

Details The number of edges in k-quasi-planar graphs The number of edges in k-quasi-planar graphs

2011-12-11

arxiv.org/abs/1112.2361v1

Mathematics

Combinatorics

arXiv admin note: substantial text overlap with arXiv:1106.0958

Scientific paper

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^{\alpha^{c_k}(n)} in the special case where the graph is drawn in such a way that every pair of edges meet at most once. Here \alpha(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 2^{ck^6}n\log n.

Affiliated with

Also associated with

No associations

Rating

The number of edges in k-quasi-planar graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The number of edges in k-quasi-planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The number of edges in k-quasi-planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-307080