Intersection Reverse Sequences and Geometric ApplicationsMarcus, Adam and Tardos, Gábor (2004) Intersection Reverse Sequences and Geometric Applications. In: Graph Drawing 12th International Symposium, GD 2004, September 29October 2, 2004 , pp. 349359(Official URL: http://dx.doi.org/10.1007/9783540318439_35). Full text not available from this repository.
Official URL: http://dx.doi.org/10.1007/9783540318439_35
AbstractPinchasi and Radoicic [1] used the following observation to bound the number of edges in a topological graph with no selfintersecting 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 selfintersecting C4 has O(n^3/2 log n) edges. Our result also implies that n pseudocircles in the plane can be cut into O(n^3/2 log n) pseudosegments, which in turn implies bounds on pointcurve incidences and on the complexity of a level of an arrangement of curves.
Actions (login required)
