k-Quasi-Planar Graphs

Suk, Andrew (2012) k-Quasi-Planar Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 21-23, 2011 , pp. 266-277(Official URL: http://dx.doi.org/10.1007/978-3-642-25878-7_26).

Full text not available from this repository.


A topological graph is k-quasi-planar if it does not contain k pairwise crossing edges. A topological graph is 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 [16] showed that every n-vertex simple k-quasi-planar graph contains at most O (n(log n)hoch 2k−4) edges. This upper bound was recently improved (for large k) by Fox and Pach [8] to n(log n)O(log k). In this note, we show that all such graphs contain at most n(log2n)2α ck(n) edges, where α(n) denotes the inverse Ackermann function and ck is a constant that depends only on k.

Item Type: Conference Paper
Additional Information: 10.1007/978-3-642-25878-7_26
Classifications: M Methods > M.600 Planar
URI: http://gdea.informatik.uni-koeln.de/id/eprint/1261

Actions (login required)

View Item View Item