Intersection reverse sequences and geometric applications

Adam Marcus, Gábor Tardos

Research output: Contribution to journalConference article

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)349-359
Number of pages11
JournalLECTURE NOTES IN COMPUTER SCIENCE
Volume3383
StatePublished - Dec 1 2004
Event12th International Symposium on Graph Drawing, GD 2004 - New York, NY, United States
Duration: Sep 29 2004Oct 2 2004

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Intersection reverse sequences and geometric applications'. Together they form a unique fingerprint.

  • Cite this