Intersection reverse sequences and geometric applications

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:113

Article

Marcus, Adam ; Tardos, Gabor

关键词: extremal combinatorics;    cyclic order;    topological graphs;    pseudocircles;   

DOI  :  10.1016/j.jcta.2005.07.002

来源: Elsevier

【 摘 要 】

Pinchasi and Radoicic [On the number of edges in geometric graphs with no self-intersecting cycle of length 4, in: J. Pach (Ed.), Towards a Theory of Geometric Graphs, Contemporary Mathematics, vol. 342, American Mathematical Society, Providence, RI, 2004] used the following observation to bound the number of edges of a topological graph without a self-crossing cycle of length 4: if we make a list of the neighbors for every vertex in such a graph and order these lists cyclically according to the order of the emanating edges, then the common elements in any two lists have reversed cyclic order. Building on their work we give an improved estimate on the size of the lists having this property. As a consequence we get that a topological graph on n vertices not containing a self-crossing C-4 has O(n(3/2) log n) edges. Our result also implies that n pseudo-circles in the plane can be cut into O(n(3/2) log n) pseudo-segments, which in turn implies bounds on point-curve incidences and on the complexity of a level of an arrangement of curves. (c) 2005 Elsevier Inc. All rights reserved.

【 授权许可】

Free