184706
20180913061807.0
978-3-642-25877-0
0302-9743
000307210800025
ISI
CONF
k-Quasi-Planar Graphs
Berlin
2012
Springer-Verlag Berlin
2012
12
Conference Papers
Lecture Notes in Computer Science
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)(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 log(2) n)2(alpha ck(n)) edges, where alpha(n) denotes the inverse Ackermann function and c(k) is a constant that depends only on k.
Suk, Andrew
193083
245211
19th Symposium on Graph Drawing
Eindhoven, NETHERLANDS
SEP 21-23, 2011
Vankreveld, M
ed.
Speckmann, B
ed.
266-277
Graph Drawing
7034
DCG
252234
U11887
oai:infoscience.tind.io:184706
SB
conf
183120
EPFL-CONF-184706
EPFL
PUBLISHED
REVIEWED
CONF