TY - JOUR

T1 - Intersection reverse sequences and geometric applications

AU - Marcus, Adam

AU - Tardos, Gábor

N1 - Funding Information:
E-mail addresses: adam@math.gatech.edu (A. Marcus), tardos@renyi.hu (G. Tardos). 1 On leave from the Department of Mathematics (ACO), Georgia Institute of Technology, Atlanta, GA 30332-0160. This research was made possible due to funding by the Fulbright Program in Hungary. 2Partially supported by the Hungarian National Research Fund grants OTKA T048826, OTKA T046234 and OTKA T037846.

PY - 2004

Y1 - 2004

N2 - Pinchasi and Radoičić used the following observation to bound the number of edges in a topological graph with no self-intersecting cycles of length 4: if we make a list of the neighbors for every vertex in such a graph and order these lists cyclicly according to the connecting edge, then the common elements in any two lists have reversed cyclic order. Building on their work we give an 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-intersecting 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.

AB - Pinchasi and Radoičić used the following observation to bound the number of edges in a topological graph with no self-intersecting cycles of length 4: if we make a list of the neighbors for every vertex in such a graph and order these lists cyclicly according to the connecting edge, then the common elements in any two lists have reversed cyclic order. Building on their work we give an 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-intersecting 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.

UR - http://www.scopus.com/inward/record.url?scp=24144433442&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=24144433442&partnerID=8YFLogxK

M3 - Conference article

AN - SCOPUS:24144433442

SN - 0302-9743

VL - 3383

SP - 349

EP - 359

JO - Lecture Notes in Computer Science

JF - Lecture Notes in Computer Science

T2 - 12th International Symposium on Graph Drawing, GD 2004

Y2 - 29 September 2004 through 2 October 2004

ER -