Intersection Reverse Sequences and Geometric Applications

Marcus, Adam and Tardos, Gábor (2004) Intersection Reverse Sequences and Geometric Applications. In: Graph Drawing 12th International Symposium, GD 2004, September 29-October 2, 2004, New York, NY, USA , pp. 349-359 (Official URL:

Full text not available from this repository.


Pinchasi and Radoicic [1] 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 C4 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.

Item Type:Conference Paper
Additional Information:10.1007/978-3-540-31843-9_35
Classifications:Z Theory > Z.750 Topology
ID Code:602

Repository Staff Only: item control page


Pinchasi, R., Radoicic, R.: On the number of edges in geometric graphs with no self-intersecting cycle of length 4. In Pach, F., ed.: Towards a Theory of Geometric Graphs. Number 342 in Contemp. Math., Providence, RI, Amer. Math. Soc. (2004)

Tamaki, H., Tokuyama, T.: How to cut pseudo-parabolas into pseudosegments. Discrete Comput. Geom. 19 (1998) 265-290

Aronov, B., Sharir, M.: Cutting circles into pseudo-segments and improved bounds for incidences. Discrete Comput. Geom. 28 (2002) 475-490

Agarwal, P., Nevo, E., Pach, J., Pinchasi, R., Sharir, M., Smorodinsky, S.: Lenses in arrangements of pseudo-circles and their applications. J. ACM 51 (2004) 139-186

Chan, T. M.: On levels in arrangements of curves. Discrete and Comput. Geom. 29 (2000) 375-393

Chan, T. M.: On levels in arrangements of curves, II: a simple inequality and its consequence. In: Proc. 44th IEEE Symposium on Foundations of Computer Science (FOCS). (2003) 544-550

Kövari, T., T. Sós, V., Turán, P.: On a problem of K. Zarankiewics. Colloq. Math. 3 (1954) 50-57

Elekes, Gy.: Sums versus products in number theory, algebra and Erdös geometry. In G. Hálász, et. al., ed.: Paul Erdös and his mathematics II. Based on the conference, Budapest, Hungary, July 4-11, 1999. Volume 11 of Bolyai Soc. Math. Stud., Springer (2002) 241-290