kQuasiPlanar GraphsSuk, Andrew (2012) kQuasiPlanar Graphs. In: Graph Drawing 19th International Symposium, GD 2011, September 2123, 2011 , pp. 266277(Official URL: http://dx.doi.org/10.1007/9783642258787_26). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783642258787_26
AbstractA topological graph is kquasiplanar 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 nvertex simple kquasiplanar 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.
Actions (login required)
