000184706 001__ 184706
000184706 005__ 20180913061807.0
000184706 020__ $$a978-3-642-25877-0
000184706 022__ $$a0302-9743
000184706 02470 $$2ISI$$a000307210800025
000184706 037__ $$aCONF
000184706 245__ $$ak-Quasi-Planar Graphs
000184706 260__ $$bSpringer-Verlag Berlin$$c2012$$aBerlin
000184706 269__ $$a2012
000184706 300__ $$a12
000184706 336__ $$aConference Papers
000184706 490__ $$aLecture Notes in Computer Science
000184706 520__ $$aA 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.
000184706 700__ $$0245211$$g193083$$aSuk, Andrew
000184706 7112_ $$dSEP 21-23, 2011$$cEindhoven, NETHERLANDS$$a19th Symposium on Graph Drawing
000184706 720_1 $$aVankreveld, M$$eed.
000184706 720_1 $$aSpeckmann, B$$eed.
000184706 773__ $$j7034$$tGraph Drawing$$q266-277
000184706 909C0 $$xU11887$$0252234$$pDCG
000184706 909CO $$pconf$$pSB$$ooai:infoscience.tind.io:184706
000184706 917Z8 $$x183120
000184706 937__ $$aEPFL-CONF-184706
000184706 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000184706 980__ $$aCONF