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 , pp. 295-311(Official URL: http://dx.doi.org/10.1007/3-540-36151-0_28).

Full text not available from this repository.

Abstract

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.

Item Type: Conference Paper
Additional Information: 10.1007/3-540-36151-0_28
Classifications: Z Theory > Z.999 Others
P Styles > P.720 Straight-line
Z Theory > Z.250 Geometry
URI: http://gdea.informatik.uni-koeln.de/id/eprint/223

Actions (login required)

View Item View Item