Geometric Graphs with No Self-intersecting Path of Length Three
Pach, János and Pinchasi, Rom and Tardos, Gábor and Tóth, Géza (2002) Geometric Graphs with No Self-intersecting Path of Length Three. In: Graph Drawing 10th International Symposium, GD 2002, August 26-28, 2002, Irvine, CA, USA , pp. 295-311 (Official URL: http://dx.doi.org/10.1007/3-540-36151-0_28).
Full text not available from this repository.
Let G be a geometric graph with n vertices, i.e., a graph drawn in the plane with straight-line edges. It is shown that if G has no self-intersecting path of length 3, then its number of edges is O(n log n). This result is asymptotically tight. Analogous questions for curvilinear drawings and for longer paths are also considered.
Repository Staff Only: item control page