$k$-quasi planar graphs

Details $k$-quasi planar graphs $k$-quasi planar graphs

2011-06-06

arxiv.org/abs/1106.0958v1

Mathematics

Combinatorics

Scientific paper

A topological graph is \emph{$k$-quasi-planar} if it does not contain $k$ pairwise crossing edges. A topological graph is \emph{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 \cite{pach} 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 \cite{fox} to $n(\log n)^{O(\log k)}$. In this note, we show that all such graphs contain at most $(n\log^2n)2^{\alpha^{c_k}(n)}$ edges, where $\alpha(n)$ denotes the inverse Ackermann function and $c_k$ is a constant that depends only on $k$.

Affiliated with

Also associated with

No associations

Rating

$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 $k$-quasi planar graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and $k$-quasi planar graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-389034