New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs

Suk, Andrew and Walczak, Bartosz (2013) New Bounds on the Maximum Number of Edges in k-Quasi-Planar Graphs. In: 21st International Symposium, GD 2013, September 23-25, 2013 , pp. 95-106(Official URL: http://dx.doi.org/10.1007/978-3-319-03841-4_9).

Full text not available from this repository.

Abstract

A 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.

Item Type: Conference Paper
Classifications: G Algorithms and Complexity > G.420 Crossings
Z Theory > Z.750 Topology
Divisions: UNSPECIFIED
Depositing User: Administration GDEA
Date Deposited: 13 Aug 2014 16:13
Last Modified: 13 Aug 2014 16:13
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1364

Actions (login required)

View Item View Item