New Bounds on the Maximum Number of Edges in kQuasiPlanar GraphsSuk, Andrew and Walczak, Bartosz (2013) New Bounds on the Maximum Number of Edges in kQuasiPlanar Graphs. In: 21st International Symposium, GD 2013, September 2325, 2013 , pp. 95106(Official URL: http://dx.doi.org/10.1007/9783319038414_9). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783319038414_9
AbstractA topological graph is kquasiplanar 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 kquasiplanar graph on n vertices is O(n). Fox and Pach showed that every kquasiplanar 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 kquasiplanar 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.
Actions (login required)
