## New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs
Suk, Andrew and Walczak, Bartosz
(2013)
Full text not available from this repository. ## AbstractA topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. An old conjecture states 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 and no pair of edges intersecting in more than O(1) points has at most n(logn) O(logk) edges. We improve this upper bound to 2α(n)cnlogn , where α(n) denotes the inverse Ackermann function, and c depends only on k. We also show that every k-quasi-planar graph with n vertices and every two edges have at most one point in common has at most O(nlogn) edges. This improves the previously known upper bound of 2α(n)cnlogn obtained by Fox, Pach, and Suk.
Repository Staff Only: item control page References |